문제

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

코드 (Java)

import java.util.*;
import java.io.*;
 
class Solution
{
    private static int[][] map;
    private static boolean[][] visited;
    private static int N, K;
    private static final int[][] delta = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
     
    public static void main(String args[]) throws Exception
    {
        //System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
        int T;
        T=Integer.parseInt(br.readLine().trim());
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[N][N];
            visited = new boolean[N][N];
            int maxHeight = -1;
             
            for (int row = 0; row < N; ++row) {
                st = new StringTokenizer(br.readLine().trim());
                for (int col = 0; col < N; ++col) {
                    map[row][col] = Integer.parseInt(st.nextToken());
                    maxHeight = Math.max(map[row][col], maxHeight);
                }
            }
             
            int maxCnt = 0;
             
            for (int row = 0; row < N; ++row) {
                for (int col = 0; col < N; ++col) {
                    if (maxHeight == map[row][col]) {
                        maxCnt = Math.max(maxCnt, dfs(row, col, 1, true));
                    }
                }
            }
             
            bw.write("#" + test_case + " " + maxCnt + "\n");
        }
        bw.flush();
        br.close();
        bw.close();
    }
     
    private static int dfs(int row, int col, int cnt, boolean canChop) {
        int maxCnt = cnt;
        visited[row][col] = true;
//      System.out.printf("called for %d %d with cnt %d\n", row, col, cnt);
         
        for (int idx = 0; idx < 4; ++idx) {
            int newR = row + delta[idx][0];
            int newC = col + delta[idx][1];
             
            if (newR >= 0 && newR < N && newC >= 0 && newC < N && !visited[newR][newC]) {
                if (map[newR][newC] < map[row][col]) {
                    //smaller. It's possible.
                    maxCnt = Math.max(maxCnt, dfs(newR, newC, cnt+1, canChop));
                } else if (canChop && map[newR][newC] - map[row][col] <= K-1) {
                    //we can chop. in this case, we should minimize the chopping.
                    int oldVal = map[newR][newC];
                    map[newR][newC] = map[row][col] - 1;
                    maxCnt = Math.max(maxCnt,  dfs(newR, newC, cnt+1, false));
                    map[newR][newC] = oldVal;
                }
            }
        }
         
        visited[row][col] = false;
         
        return maxCnt;
    }
}

풀이

• 앞문제랑 반대로 DFS에 최적화된 문제고, 내 생각에 BFS로 푸는 것은 불가능하다. 재귀 형식으로 해도 스택에 문제는 없어서 그렇게 구현했다.

• 유의해야하는 조건은 바로 산을 깎는 경우다. K도 고려해야 하고, 애초에 산을 깎는 횟수가 남아있는지도 고려해야 하며, 깎은 후의 높이로 진행을 해야한다는 것도 유의. 첫번째는 직접 비교, 두번째는는 재귀하면서 전달하는 형태로, 세번째는 깎은 값을 지도에 반영했으며 이 때 깎았던 것을 (탐색 완료 후) 다시 원래대로 둬야 한다는 것도 유의.

• 또 visited를 참으로 했다가 거짓으로 했다가 하는 응용도 약간 필요하다.