[SWExpertAcademy] 1949번 등산로 조성 C++

문제 : N * N 크기의 부지에 최대한 긴 등산로 만들기

<과정>

1. 등산로는 가장 높은 봉우리에서 시작.

2. 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결. (높이가 같거나 낮은 지형이거나 대각선 방향 연결 불가능)

3. 한 곳을 골라 최대 K 깊이 만큼 지형 깎기 공사 가능.

 

- 입력

지도 크기 N, 최대 공사 가능 깊이 K

N * N의 지도 정보

 

- 출력

만들 수 있는 가장 긴 등산로의 길이

 

- 제약사항

3 ≤ N ≤ 8, 1 ≤ K ≤ 5, 1 ≤지형의 높이 ≤ 20

가장 높은 봉우리 최대 5개

지형은 정수 단위로만 깎기

지형 높이 1보다 작게 만들기 가능

---

문제 이해

N * N 크기의 지도에서 등산로를 만들고, 그 중에서 가장 긴 등산로의 길이를 찾자!

 

접근 방법

DFS 사용해서 등산로를 만들 수 있는 모든 경로들을 살피고, 그 과정에서 가장 긴 등산로를 찾아야할 것이다. 그런데 주의할 부분은 지형 중에서 한 곳만을 골라 최대 K까지 깎는 공사를 할 수 있는데 이걸 최대 K로 깎으면 다음에 가야할 지형의 높이의 값도 작아지게 되고 추후에 갈 수 있는 지형의 개수도 줄어들기 때문에 무조건 K로 깎는다고 하면 안 된다.

 

코드

#include <iostream>
#include <cstring>
using namespace std;

int T;
int N, K;
int MAP[9][9];
int visited[9][9];
struct Block {
	int y;
	int x;
	int h;
	int isDigged;
	int len;
};
int diry[4] = { -1,1,0,0 };
int dirx[4] = { 0,0,-1,1 };

int result;

void makeRoad(Block block) {
	
	if (result < block.len)
		result = block.len;

	for (int i = 0; i < 4; i++) {

		int ny = diry[i] + block.y;
		int nx = dirx[i] + block.x;
		int nh = MAP[ny][nx];

		if (ny < 0 || nx < 0 || ny >= N || nx >= N)
			continue;
		if (visited[ny][nx] == 1)
			continue;

		if (nh < block.h) {
			visited[ny][nx] = 1;
			makeRoad({ ny, nx, nh, block.isDigged, block.len + 1 });
			visited[ny][nx] = 0;
		}
		else {
			if (block.isDigged != 1 && nh - K < block.h) {
				visited[ny][nx] = 1;
				nh = block.h - 1;
				makeRoad({ ny, nx, nh, 1, block.len + 1 });
				visited[ny][nx] = 0;
			}
		}
	}


}

int main() {
	
	cin >> T;

	for (int t = 1; t <= T; t++) {
		cin >> N >> K;
		
		int top = -21e8;
		/*
		vector<Block> topBlocks;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> MAP[i][j];
				if (MAP[i][j] >= top) {
					topBlocks.push_back({ i,j });
				}
			}
		}이렇게 하면 안되네.. 나중에 top 값이 갱신되면 그 이전에 들어간 값들도 모두 top으로 취급됨.
		*/
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> MAP[i][j];
				if (MAP[i][j] >= top) top = MAP[i][j];
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (MAP[i][j] == top) {
					visited[i][j] = 1;
					Block block = { i, j, top, 0, 1 };
					makeRoad(block);
					visited[i][j] = 0;

				}
			}
		}

		cout << '#' << t << ' ' << result << endl;
		result = 0;
		memset(visited, 0, sizeof(visited));
		memset(MAP, 0, sizeof(MAP));
	}

}

MAP입력을 받을 때에 가장 높은 지형을 vector에 넣어서 그 vector만 돌리려고 했는데 중간에 top 값이 갱신되면 그 이전에 top이라고 들어간 값들은 모두 의미가 없어지기 때문에 따로 처리하거나 vector를 사용해서는 안 됨. 

테스트 케이스마다 result 초기화 주의.

makeRoad에 다음 block 정보를 넣어줄 때, isDigged는 현재까지 팠는지 안팠는지의 여부를 넣어주는 것이므로 그대로 받아서 사용해주자.

block을 깎게 될 때에는 1만 깎는 것이 가장 긴 등산로를 만들 수 있음을 기억하자.

 

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq 

SW Expert Academy