[SWEA] 1949. 등산로 조성 (JAVA)

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

1. 등산로는 가장 높은 봉우리에서 시작해야하므로 지도를 입력하면서 가장 높은 봉우리를 구한다.

2. 가로 또는 세로 방향으로 연결 되어야 하므로 사방탐색을 한다. 높이가 낮은쪽으로만 이동할 수 있다.

3. 딱 한 곳을 정해서 최대 K 만큼 깎을 수 있다.

     -> 여기서 생각을 많이 했는데, 최대 K 만큼 깎을 수 있으므로 이동할 봉우리에서 K만큼 뺐을 때 현재 봉우리보다 작으면 이동이 가능하며, 이동할 봉우리를 현재 봉우리보다 1만큼 작은 수가 되도록 깎아주면 된다. 1부터 K만큼 계속 깎을 필요가 없다 !

4. 봉우리를 깎으면서 재방문 할 수도 있으므로 방문처리를 해주어야한다.

5. answer을 갱신해준다.

import java.util.*;
import java.io.*;

public class Solution
{

    static int N, K;
    static int[][] map;
    static boolean[][] visited;
    static int highest;
    static int answer;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};
    
    public static void dfs(int x, int y, int len, boolean cut){
        //최대 길이 갱신
        answer = Math.max(len,answer);
        //방문처리
        visited[x][y]=true;

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

            if(isIn(nx,ny)&&!visited[nx][ny]){
                if(map[nx][ny]<map[x][y]){
                    //원래 갈 수 있는 길이면
                    dfs(nx,ny,len+1,cut); //가본다.
                }
                else{
                    if(!cut && map[nx][ny]-K<map[x][y]){
                        int tmp = map[nx][ny];
                        map[nx][ny] = map[x][y]-1;
                        dfs(nx,ny,len+1,true);
                        map[nx][ny] = tmp;
                    }
                }
            }
        }
        visited[x][y] = false;
    }

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

    public static void main(String args[]) throws Exception
    {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T;
        T=Integer.parseInt(br.readLine());


        for(int test_case = 1; test_case <= T; test_case++)
        {
            sb.append('#').append(test_case).append(' ');
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            highest = Integer.MIN_VALUE;
            answer = Integer.MIN_VALUE;
            map = new int[N][N];
            visited = new boolean[N][N];

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

            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if(map[i][j]==highest){
                        dfs(i,j,1,false);
                    }
                }
            }
            sb.append(answer).append('\n');
        }
        bw.write(sb.toString());
        bw.close();
    }
}

3번 조건을 이해하는데에 조금 시간이 걸렸던 문제이다.