[SWEA] 모의 SW 역량테스트 1949번 등산로 조성 (JAVA)

문제 출처 - SW Expert Academy

문제는 여기

SW Expert Academy

[문제] 

등산로를 조성하려고 한다.
등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.
등산로 부지는 아래 [Fig. 1]과 같이 숫자가 표시된 지도로 주어지며, 각 숫자는 지형의 높이를 나타낸다.

등산로를 만드는 규칙은 다음과 같다.
   ① 등산로는 가장 높은 봉우리에서 시작해야 한다.
   ② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
       즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.
   ③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.
N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.
이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.
그 다음 N개의 줄에는 N * N 크기의 지도 정보가 주어진다.

[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.

 

 

---

[풀이]

1. 최고 높이를 구해준다.

2. 최고 높이와 같은 경우에 DFS 탐색을 한다.

3. DFS 탐색을 하면서 현재 높이보다 높은 경우와 아닌 경우로 분리해서 DFS를 탐색한다.
4. 현재보다 높은 경우 깎을 횟수가 있는지, 깎았을 때 현재 높이보다 낮아지는지를 확인 후 가능하다면 추가 탐색

5. 현재보다 낮은 경우라면 계속 탐색을 진행

[접근]

1. 완전 탐색을 하는데 BFS, DFS 어떤 것을 사용하는가?를 고민

2. BFS보다는 DFS가 쉽게 풀릴 거 같아서 DFS를 선택함

3. DFS를 탐색하면서 높이를 깎을 때 얼마만큼을 깎아야 하는지 고민

4. 생각을 해보니 산을 깎았을 때 현재 높이의 -1만큼만 깎아야 다음에 가장 높은 높이가 된다.

[코드]

package swet;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution_test_1949 {
	static int T;
	static int n;
	static int k;
	static int[][] map;
	static boolean[][] visited;
	static int max_height; // 최고 높이
	static int result; // 결과
	
	static int[] dr = {1, -1, 0, 0};
	static int[] dc = {0, 0, 1, -1};
	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			n = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			
			// 전체 초기화
			map = new int[n][n];
			visited = new boolean[n][n];
			max_height = 0;
			result = 0;
			
			// 값을 입력받기
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					// 입력받으면서 최고 높이 갱신
					max_height = Math.max(map[i][j], max_height);
				}
			}
			
			// dfs를 돌릴껀데 최고높이에서 돌려야하니까
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (map[i][j] == max_height) { // 최고높이라면
						// 탐색
						visited[i][j] = true;
						dfs(i, j, map[i][j], 1, 1);
						// x좌표, y좌표, 시작점의 높이, 산을 깎을 수 있는 횟수, 이동 횟수
						visited[i][j] = false;
					}
				}
			}
			
			System.out.println("#" + t + " " + result);
		}
	}

	/*
	 * x, y의 좌표, 높이, 산을 깎은 횟수, 이동 횟수
	 */
	public static void dfs(int x, int y, int height, int cnt, int move) {
		for (int i = 0; i < 4; i++) {
			if (result < move) {
				result = move;
			}
			
			int nx = x + dr[i];
			int ny = y + dc[i];
			
			if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
				// 범위 안에 있으면서 방문하지 않았다면
				if (height <= map[nx][ny]) {
					// 가야할 곳의 높이가 현재의 높이보다 높다면
					if (cnt == 1 && height > map[nx][ny] - k) {
						// 깎을 횟수가 남아 있고 깎았을 때 현재 높이 보다 낮아진다면
						visited[nx][ny] = true;
						dfs(nx, ny, height - 1, cnt - 1, move + 1);
						visited[nx][ny] = false;
					}
				}
				else { // 가야할 곳의 높이가 현재 높이보다 작으니까
					visited[nx][ny] = true;
					dfs(nx, ny, map[nx][ny], cnt, move + 1);
					visited[nx][ny] = false;
				}
			}
		}
	}
}

[실수]

1. DFS를 돌면서 result보다 move가 클 때, 값을 변경해주고 return을 시켰는데 추가 탐색을 할 수 있는 경우에도 return을 해서 탐색이 종료되는 경우가 발생했다.

2. DFS 탐색을 하면서 인자 값을 넘겨줄 때, cnt로 넘겨주지 않고 0, 1로 넘겨줘 깎았는데 이후에 또 깎을 횟수가 생기는 경우가 발생했다.