[SWEA Java] 1949. 등산로 조성

기본 등산로 조성은 dfs로 4방향에서 갈 수 있다면 방문처리 해주고 가는 방식으로 짰는데

산을 깎는 경우를 잘 모르겠다.

그냥 N만큼 i,j for문 돌리고 그 안에서 K만큼 반복문 돌려서 다 깎아봤어도 시간 초과가 안 났을 것 같은데 풀다보니 이렇게 풀게 됐다.

 

정리

❗️현재 높이와 다음 높이를 비교했을 때, 작은 경우와 큰 경우를 따로 생각한다.

❗️큰 경우라면 이전에 깎았는지 확인하고 안깎깎 ? 깎 : 안깎처리를 해준다.

❗️다음 높이가 높을 때 깎는 높이는 현재 높이에서 1만 깎으면 된다. 물론 K만큼 깎았을 때 현재 높이보다 낮아야 한다. 이거 이해하는데 오래 걸렸다

❗️방문처리! 깎은 산! 복원이 중요했다. 갔다 왔으면 원래대로 돌려주자.

❗️제일 높은 봉우리만 시작이 됨.

 

코드

package SWEA;

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

public class Solution_1949_등산로조성 {

    static int N, K, res;
    static int[][] map;
    static boolean[][] v;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            tokens = new StringTokenizer(br.readLine());
            N = Integer.parseInt(tokens.nextToken());
            K = Integer.parseInt(tokens.nextToken());

            map = new int[N][N];
            v = new boolean[N][N];
            int max = 0;

            for (int i = 0; i < N; i++) {
                tokens = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(tokens.nextToken());
                    if (max < map[i][j]) max = map[i][j];
                }
            } // end input

            res = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == max) {
                        dfs(i, j, 1, true);
                    }
                }
            }
            sb.append("#").append(tc).append(" ").append(res).append("\n");
        } // end test case
        System.out.println(sb);
    }

    private static void dfs(int x, int y, int len, boolean flag) {
        v[x][y] = true;
        for (int d = 0; d < 4; d++) {
            int nx = x + dr[d];
            int ny = y + dc[d];

            // 범위 밖, 방문이면 다음 방향
            if (!isRange(nx, ny) || v[nx][ny])
                continue;

            //다음 높이가 현재 높이보다 작을때
            if (map[nx][ny] < map[x][y]) {
                dfs(nx, ny, len + 1, flag);
            } else {//다음 높이가 현재 높이보다 같거나 크고 깎을 수 있을 때
                if (flag && map[nx][ny] - K < map[x][y]) {
                    int temp = map[nx][ny];
                    v[nx][ny] = true;
                    map[nx][ny] = map[x][y]-1;
                    dfs(nx, ny, len + 1, false);
                    map[nx][ny] = temp;
                    v[nx][ny] = false;
                    flag = true;
                }
            }
        }
        v[x][y] = false;
        // 더이상 갈 수 없으면 거리 갱신
        res = Math.max(res, len);
    }

    private static boolean isRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N)
            return false;
        return true;
    }
}