[Java] SWEA 등산로 조성

1. 문제 분석

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

SW Expert Academy

높은 곳부터 시작해서 점차 낮은 곳으로 길을 찾는 문제다.

딱 1곳에만 깎을 수 있고 등산로의 길이가 가장 긴 곳을 고르면 된다.

싸피 수업시간에는 문제가 제대로 이해안갔지만 이제는 그냥 이해를 해버렸다.

 

접근은 다음과 같다.

1. DFS 사용

2. 만약 길을 못간다면 깎아서 갈 수 있는지를 확인 -> 여기서 최소한으로 깎아야함

3. 더이상 깎지 못하게 적용

4. DFS 시작할 때 현재까지 경로의 길이를 갱신

 

볼드체로 된 부분이 가장 헷갈렸다. 처음은 최대 깎을 수 있는 것을 뺐지만 이렇게 하면 최대한 긴 경로가 안나온다.

(테케는 전부다 통과해서 조심해야한다.)

그래서 더 많은 경로를 갈 수 있도록 깎는 높이를 다시 구해야 한다.

2. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static int size;
    static int[][] map;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int deleteHeight;
    static int answer = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());

        for (int c = 1; c <= tc; c++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            size = Integer.parseInt(st.nextToken());
            deleteHeight = Integer.parseInt(st.nextToken());

            map = new int[size][size];

            int max = 0;
            for (int i = 0; i < size; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < size; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    max = Math.max(map[i][j], max);
                }
            }

            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (map[i][j] == max) {
                        //dfs
                        boolean[][] visited = new boolean[size][size];
                        visited[i][j] = true;
                        dfs(j, i, 1, 1, visited, max);
                    }
                }
            }
            System.out.println("#" + c + " " + answer);
            answer = Integer.MIN_VALUE;
        }
    }

    static void dfs(int x, int y, int dist, int deleteCount, boolean[][] visited, int height) {

        answer = Math.max(answer, dist);

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

            if (mx < 0 || my < 0 || mx >= size || my >= size) continue;
            if (visited[my][mx]) continue;

            //만약 더 큰 벽이 존재한다면?
            if (height <= map[my][mx]) {
                //깎을 기회가 존재하고 깎았을때 조건에 만족하면?
                if (deleteCount == 1 && map[my][mx] - deleteHeight < height) {
                    int calc = 0;
                    for(int j = 1; j<=deleteHeight; j++){
                        if(map[my][mx] - j < height) {
                            calc = map[my][mx] - j;
                            break;
                        }
                    }
                    visited[my][mx] = true;
                    dfs(mx, my, dist + 1, deleteCount - 1, visited, calc);
                    visited[my][mx] = false;
                }
            }
            //그냥 가능
            else {
                visited[my][mx] = true;
                dfs(mx, my, dist + 1, deleteCount, visited, map[my][mx]);
                visited[my][mx] = false;
            }
        }
    }
}

DFS 자체는 쉽게 나왔지만 한번 생각을 해야했다.

3. 마무리

DFS를 너무 오랜만에 풀어서 그런지 까먹어서 답지를 보긴했다.

근데 답지는 죄다 높이에서 1을 빼주던데 이러면 현재 높이 5, 깎을 수 있는 범위 3, 주변높이 7,7,7,7 일때 걸리지 않나?

그래서 높이를 구했더니 답은 같았다.