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

SW Expert [모의 SW 역량테스트] 1949번 등산로 조성 : 

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

 

 

최대 등산로의 길이를 찾는 dfs + 브루트 포스 문제이다.

각 위치에서 최대 K만큼 지형을 깎을 수 있다.

K만큼 지형을 깎을 수 있다는 조건이 어렵게 느껴질 수 있으나,

그냥 최대 등산로의 길이를 찾는 로직을 K번 반복해주면 된다.

 

전체적인 흐름은 아래와 같다.

   1. 2중 for문을 사용해서 map에서의 index를 하나 지정한다.

   2. 해당 위치에서 0~K만큼의 지형을 깎는다.

   3. 미리 받아둔 최고점의 위치에서 dfs로 탐색한다.

   4. 2번에서 깎은 지형만큼 다시 원상복구 시킨 후 2번으로 돌아간다.

   5. 0~K 모든 경우에 대해서 체크 했다면 1번으로 돌아간다.

 

등산로를 정하는 조건이 해당 위치보다 낮은 경우로만 이동할 수 있기 때문에,

평소에 사용하던 visit 함수도 필요 없었다.

 

 

코드

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

public class Main {
    private static int N, K, answer;
    private static int[][] map;
    private static ArrayList<int[]> high;
    private static int[] dx = {0, 0, -1, 1};
    private static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws Exception {
        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];
            high = new ArrayList<>();
            answer = 0;

            int max = Integer.MIN_VALUE;
            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 = Math.max(max, map[i][j]);
                }
            }

            for (int i = 0; i < N; i++) { // 최고점 위치 저장
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == max) high.add(new int[]{i, j});
                }
            }

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

    private static void solution() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k <= K; k++) {
                    map[i][j] -= k;
                    for (int idx = 0; idx < high.size(); idx++) { // 최고점에서의 탐색
                        int sx = high.get(idx)[0];
                        int sy = high.get(idx)[1];
                        dfs(sx, sy, 1);
                    }
                    map[i][j] += k;
                }
            }
        }
    }

    private static void dfs(int x, int y, int count) {
        int nx, ny;
        boolean flag = false;
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];

            if (!isValid(nx, ny)) continue;

            if (map[x][y] > map[nx][ny]) {
                flag = true;
                dfs(nx, ny, count + 1);
            }
        }
        if (!flag) answer = Math.max(answer, count); // 더 이상 이동할 수 없음.
    }

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