[SWEA]1949.등산로 조성

dfs + 완전탐색으로 풀었다.

 

처음엔 백준의 벽 부수고 이동하기와 비슷하다고 생각해서 bfs로 접근했지만 가능한 길게 등산로를 만들어야 하기 때문에 dfs로 푸는게 일반적인 풀이라는 것을 알았다. 

 

• 봉우리들을 찾는다.
• 봉우리마다 등산로 조성을 해본다.
• 인접한 곳이 내리막길이 아니면 1씩 깎아보면서(K까지만) 내리막이 되면 탐색을 계속한다.

먼저 맵에서 가장 높은 곳의 높이를 highest에 저장하고 그 지점들을 peak배열에 삽입한다. peak배열에서 봉우리를 하나씩 꺼내서 탐색을 한다. 

 

탐색을 할 때 이전에 지형을 깎는 공사를 했는지 안했는지 여부를 체크하기 위해 flag 변수를 사용한다. 지형을 깎는 공사를 이미 했다면 더 이상 깎는 공사를 할 수 없으므로 현재 지점보다 낮은 지점으로만 탐색을 계속해나간다. 공사를 아직 안했는데 현재 지점보다 높거나 같은 높이의 지점을 만나면 최대 K까지 1씩 깎아보면서 현재지점보다 낮아지면 탐색을 계속해나간다. 

 

등산로의 길이는 dfs를 시작할때 ++ 해주고 끝날때 최대 길이를 갱신하고 다시 원래대로 돌려놓는다.즉, 길이를 -- 해주고 방문여부를 false로 바꾼다. dfs문제에서 이것처럼 다시 원래 상태로 돌려놓는 것이 중요한 포인트이다. 지형 깎는 공사를 할 때도 dfs가 끝나면 깎아준 값 만큼 다시 더해서 원래대로 돌려놓고 flag도 false로 갱신하여 다음 탐색을 할 수 있도록 해야한다. 

 

 

private static void dfs(int curX, int curY) {

		visited[curY][curX] = true;
		length++;

		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i];
			int nextY = curY + dy[i];

			if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N) {

				if (flag) { // 깎기 이미 한 경우.

					if (map[nextY][nextX] < map[curY][curX] && !visited[nextY][nextX]) { // 내리막인 경우 
						dfs(nextX, nextY);
					}

				} else { // 아직 안 깎은 경우.

					if (map[nextY][nextX] < map[curY][curX] && !visited[nextY][nextX]) { // 내리막인 경우 
						dfs(nextX, nextY);
					}

					if (map[nextY][nextX] >= map[curY][curX] && !visited[nextY][nextX]) { // 오르막인 경우 
						for (int depth = 1; depth <= K; depth++) { // 1씩 깎아본다 
							if (map[nextY][nextX] - depth < map[curY][curX]) {
								map[nextY][nextX] -= depth;
								flag = true;
								dfs(nextX, nextY);
								// 원래대로 만들기 
								map[nextY][nextX] += depth;
								flag = false;
							}
						}
					}
				}

			}
		}
		max = Math.max(max, length);
		// 원래대로 만들기 
		length--;
		visited[curY][curX] = false;
	}

 

<전체코드>