[DFS/BFS] 1949. 등산로 조성 (Java)

[SWEA] 1949. 등산로 조성

📌 풀이 과정

📝 문제 규칙

① 등산로는 가장 높은 봉우리에서 시작해야 한다.

② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.

③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.

📝 DFS 탐색 과정

1. 가장 높은 봉우리에서 탐색을 시작한다
   먼저, 지도에서 가장 높은 봉우리를 찾아 그곳에서 탐색을 시작한다. 여러 개의 최고 봉우리가 있을 경우, 각각의 봉우리에서 DFS 탐색을 진행한다.

2. 다음 봉우리로의 이동 조건

   • 현재 봉우리의 높이가 다음 봉우리보다 높은 경우
     바로 다음 봉우리로 이동하여 탐색을 계속한다.

   • 현재 봉우리의 높이가 다음 봉우리와 같거나 더 낮은 경우
     공사를 통해 깎을 수 있는 기회가 남아 있을 때만, 1 ~ K의 범위만큼 깎아서 탐색을 진행한다.
     단, 깎은 후의 봉우리가 현재 봉우리보다 작은 경우에만 탐색이 가능하다.

3. 최대 깊이 갱신
   DFS 탐색이 진행될 때, 현재 탐색한 경로의 깊이(depth)가 이전에 기록한 최대 깊이(ans)보다 크면 ans 값을 갱신한다.

✨ 제출 코드

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

public class Solution {

    static int N, K, ans, high;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            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];
            high = 0;
            ans = 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());
                    high = Math.max(high, map[i][j]);
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == high) {
                        visited[i][j] = true;
                        dfs(i, j, 1, false); // cut을 boolean으로 처리 (false: 아직 안깎음)
                        visited[i][j] = false;
                    }
                }
            }

            System.out.println("#" + t + " " + ans);
        }
    }

    static void dfs(int x, int y, int depth, boolean cut) {

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

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

            if (map[x][y] > map[nx][ny]) { // 현재 봉우리 > 다음 탐색할 봉우리
                visited[nx][ny] = true;
                dfs(nx, ny, depth + 1, cut);
                visited[nx][ny] = false;
            }
            
            if (map[x][y] <= map[nx][ny] && !cut) { // 아직 깎지 않은 경우에만
                for (int j = 1; j <= K; j++) {
                    if (map[nx][ny] - j < map[x][y]) { // 공사를 해서 갈 수 있는 경우
                        map[nx][ny] -= j;
                        dfs(nx, ny, depth + 1, true); // 깎은 후에는 cut=true
                        map[nx][ny] += j;
                    }
                }
            }
        }

        ans = Math.max(ans, depth); // 최댓값 갱신
    }
}

문제를 좀 더 단순하게 접근하는 연습을 해야겠다!!