[SWEA SW Expert Academy] 1949. [모의 SW 역량테스트] 등산로 조성 (JAVA)

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

SW Expert Academy

등산로 조정이라는 문제는 DFS를 활용을 해서 문제를 해결해야 하는 문제입니다.

 

먼저 문제에 대해 간단하게 설명을 하면, 아래와 같은 배열이 있습니다.

 

등산로를 만들기 위해서 가장 높은 곳에서 아래로 내려가면서 등산로를 만들게 되며 이때, 현재 위치보다 반드시 작아야 합니다.

 

그런데 예외 사항으로 한칸만 K만큼 깍아서 현재보다 낮게 만들수 있습니다.

아래에 등산로 처럼 9가 가장 높은 곳임을 알 수 있습니다.

 

그래서 산을 깍지 않고, 등산로를 만들게 되면, 총 5칸의 등산로를 만들수 있습니다.

 

하지만 아래와 같이 9였던 높이를 1만큼 깍아서 현재보다 작게 만들어 등산로를 만들게 되면 아래와 같이 6칸의 등산로를 만들수 있습니다.

이러한 특징을 활용해서 문제를 해결해야 합니다.

문제에서 주어진 위의 입력값과 출력값을 활용해서 문제를 해결해야 합니다.

 

먼저 주어진 입력값을 받아주고, 배열을 만들어 줍니다.

 

그리고 등산은 가장 높은곳에서 시작해야 하므로 가장 높은 곳의 높이를 찾아줍니다.

 

그렇게 정해진 높이부터 시작을 해서 등산로를 만들어주게 됩니다.

 

이때 DFS를 활용을 해서 등산로를 하나씩 만들어 줄때마다 호출을 해서 새로운 길을 만들어주고, 더이상 만들 수 있는 길이 없다면 다시 되돌아 갈 수 있도록 해서 가장 긴 등산로를 찾게 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    private static int N, K, arr[][], mxCnt;
    private static boolean visited[][];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
 
        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            arr = new int[N][N];
 
            int answer = 0;
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            answer = solution();
            System.out.println("#" + t + " " + answer);
 
        }
    }
 
    private static int solution() {		// 가장 높은 곳을 찾고, 높은 곳에서부터 등산로를 만든다.
        int top = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                top = Math.max(top, arr[i][j]);
            }
        }
        visited = new boolean[N][N];
        mxCnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == top) {
                    visited[i][j] = true;
                    dfs(i, j, 1, false);
                    visited[i][j] = false;
                }
            }
        }
        return mxCnt;
    }
 
    private static int dx[] = { -1, 1, 0, 0 };
    private static int dy[] = { 0, 0, -1, 1 };
 
    private static void dfs(int i, int j, int cnt, boolean dig) {
        mxCnt = Math.max(mxCnt, cnt);
 
        for (int k = 0; k < 4; k++) {	//사방탐색
            int x = i + dx[k];
            int y = j + dy[k];
            if (x < 0 || x >= N || y < 0 || y >= N || visited[x][y]) {
                continue;
            }
            visited[x][y] = true;
            if (arr[x][y] < arr[i][j]) {	//현재보다 작다면
                dfs(x, y, cnt + 1, dig);
            } else if (dig == false && K >= (1 + arr[x][y] - arr[i][j])) {
            // 깍을 수 있으며, 깍았을 때 현재보다 작을 경우
                int tmp = arr[x][y];
                arr[x][y] = arr[i][j] - 1;
                dfs(x, y, cnt + 1, true);
                arr[x][y] = tmp;
            }
            visited[x][y] = false;
        }
    }
}