[코딩 테스트 RUN] SWEA 수업 : 25052. 등산로

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

[SW Expret Academy] 25052. 등산로

SW Expert Academy

 

1차적으로는 델타 이동을 사용한다. 재귀는 반드시 사용하지 않아도 되지만, 해두는 것이 편하긴 하다. 모든 길을 탐색해야 하기 때문에 그리디 등은 불가능하고, 완전탐색 형이라고 할 수 있다.

나는 재귀를 위해서 아래처럼 세팅했다.

 

            int maxPath = 0;
            //일단 2중 배열 설계하여 하나씩 봐야함
            for (int x = 0; x < N; x++) {
                for (int y = 0; y < N; y++) {
                    maxPath = Math.max(maxPath, minRoute(x,y));
                }
            }

 

 

x와 y의 길에서 시작하여 각각의 maxPath를 구해나가는 방식이다. 여기서 재귀를 사용했다. 보다시피 minRoute에는 x와 y를 각 인자값으로 넣어둔 것이다.

 

    static int minRoute(int x, int y) {
        int minValue = arr[x][y]; //(기준점)
        int minNx = -1, minNy = -1; //min값을 설정

        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 && arr[nx][ny] < minValue){
                minValue = arr[nx][ny];
                minNx = nx;
                minNy = ny;
            }

        }

        if(minNx == -1) return 1; // 자기자신이 제일 낮을 경우 자기 칸만 반환한다
        return minRoute(minNx, minNy) + 1; //자기자신 포함

    }

 

위와 같은 minRoute 재귀 함수가 존재한다.

제일 적은 값은 자기자신으로 따지고(자기자신에서 이동하기 때문에) minNx와 minNy를 만들었다. 이것은 자기자신을 체크하기 위함이며, 다음 칸(들어갈 다음칸)을 재귀 인자로 넣기 위함이다. 여기서 델타 이동이 적용된다.(따라서 델타 이동 배열의 경우 static 값으로 전역변수 처리해주는 것으로 했다) 그리고 이에 따라 경계값을 확인한다.

 

return에서 +1하는 까닭은 하나씩 늘어나기 때문. 이렇게 자기자신만 존재할때까지 반복하는 것이다.

 

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    static int N;
    static int[][] arr;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

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

        for(int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());

            arr = new int[N][N];

            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            } //세팅 완료

            int maxPath = 0;
            //일단 2중 배열 설계하여 하나씩 봐야함
            for (int x = 0; x < N; x++) {
                for (int y = 0; y < N; y++) {
                    maxPath = Math.max(maxPath, minRoute(x,y));
                }
            }
            sb.append("#").append(test_case).append(" ").append(maxPath).append("\n");
        }

        System.out.print(sb);
    }

    static int minRoute(int x, int y) {
        int minValue = arr[x][y]; //(기준점)
        int minNx = -1, minNy = -1; //min값을 설정

        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 && arr[nx][ny] < minValue){
                minValue = arr[nx][ny];
                minNx = nx;
                minNy = ny;
            }

        }

        if(minNx == -1) return 1; // 자기자신이 제일 낮을 경우 자기 칸만 반환한다
        return minRoute(minNx, minNy) + 1; //자기자신 포함

    }

}