[SWEA 1949] 등산로 조정

문제

가장 높은 곳에서 시작해서 현재 위치 이하인 높이로만 길을 탐색 할 수 있을 때, 최대로 갈 수 있는 길의 길이를 찾는다.
단 1번 높이를 깎을 수 있다.
이 때 깎은 후의 높이가 1보다 작아도 상관 없다.

풀이 방법

가장 높은곳에서만 시작 할 수 있으므로 map의 가장 높은 곳들을 찾아서 dfs를 시작 한다.
dfs로 상하좌우 탐색하면서 현재 위치 보다 낮은 곳으로 이동한다.
높이를 깎는 것은 1회만 가능 하기 때문에 ,이 경로로 도달하는 동안 길을 깎았는지를 체크할 boolean 변수 하나를 설정해 주었다.
높이는 최대 K까지 깎을 수 있으므로 0~K 만큼 깎아본 경우를 모두 따져본다.

코드

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

public class Solution_1949_등산로조정2 {
    static int N,K;
    static int[][] map ;
    static boolean[][] visited;
    static int maxLen;
    static List<int[]> top ;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        for(int tc=1;tc<=T;tc++) {
             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];
             top = new ArrayList<>();

             int m = 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());
                     m = Math.max(m, map[i][j]);
                 }
             }
             for(int i=0;i<N;i++) {
                 for(int j=0;j<N;j++) {
                     if(map[i][j]==m) {
                         top.add(new int[] {i,j});
                     }
                 }
             }
            maxLen =0;
             for(int i=0;i<top.size();i++) {
                 int[] now = top.get(i);
                 visited[now[0]][now[1]]=true;
                 flag =true;
                 dfs(1,now[0],now[1]);
                 visited[now[0]][now[1]]=false;

             }


            System.out.printf("#%d %d\n",tc,maxLen);
        }

    }
    static boolean flag;

    private static void dfs(int L, int x, int y) {
        if(L>maxLen) maxLen = L;
        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]) {
                if(flag) {
                    for(int k=0;k<=K;k++) {
                        if(map[nx][ny]-k < map[x][y]) {
                            visited[nx][ny]=true;
                            map[nx][ny]-=k;
                            flag = false;
                            dfs(L+1,nx,ny);
                            flag = true;
                            map[nx][ny]+=k;
                            visited[nx][ny]=false;
                        }
                    }
                }
            }else {
                visited[nx][ny]=true;
                dfs(L+1,nx,ny);
                visited[nx][ny]=false;
            }

        }

    }

}