[SW Expert] 1949. [모의 SW 역량테스트] 등산로 조성

생각

2차 배열로 주어진 등산로에서 가장 긴 등산로를 찾는 문제이다. 등산로는 높은 숫자에서 낮은 숫자로만 이동할 수 있다. 이 때, K 값이 주어지는데 이 K는 한 등산로를 만들 때 한 번만 사용할 수 있는 지형을 파괴할 수 있는 높이이다. 만약 처음 등산로가 9로 시작하면 근처에 있는 9로는 못가게되지만 파괴를 한 번 할 수 있는 기회를 사용해서 K=1 일 경우 다음 9를 8로 만들어서 진행 할 수 있다.

처음 생각

우선 List를 이용해서 처음에 등산로의 숫자를 입력받는 부분에서 가장 높은 숫자가 나오면 List에 추가해 주어 등산로의 출발 경로를 설정하였다.

▶ Max가 바뀔 경우 List를 초기화 하여 이전 출발 경로들을 없애고 새로 넣어준다.

다음 생각

등산로의 출발 점을 하나씩 DFS 탐색하면서 가장 길게 나갈 수 있는 등산로를 색출해 낸다. data용 inner class를 하나 만들어 정보들을 관리하였다.

다다음 생각

이전 값이 파괴를 해서 넘어온 값이라면 그 값은 원래 배열의 값이 아니므로 tempK를 통해 얼만큼 파괴했는지를 다음으로 넘겨주어 이 부분을 관리하였다.

▶ 파괴를 하지 않았을 경우 tempK = 0을 넣어주어 원래 배열의 값이 변하지 않는다. K 만큼만 파괴할 수 있는지 알았던 부분이 실수였다. 1~K 까지 파괴할 수 있었다. 가장 작은 값으로 파괴하여 높은 숫자를 유지하는것이 긴 등산로를 만들 수 있다.

다다다음 생각

방문 표시를 따로 안해주었는데 그 이유는 숫자가 차례대로 큰 수에서 작은 수로 나아가기 때문에 다시 안돌아 갈 것이라 생각하였다.

▶ 이 문제를 푸는데 가장 큰 잘 못이었다. 왜 예제 몇 개가 제대로 안나오는지 많은 시간을 들였다. 만약 4 - 3 - 2 로 등산로를 탐색하고 있고, 파괴 기회를 안 썻고 K=2일 경우 4 - 3 - 2 - 3 식으로 2에서 다시 3으로 거슬러 올라가버린 것이다. 

방안

1) K의 파괴 경우를 한 경우 하지 않은 경우의 변수를 관리해주었다.

2) 다시 거슬러 올라가는 일이 발생하지 않도록 방문 배열을 만들어 주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
class Solution{
    static int n,k;
    static int[][] arr;
    static List<Pair> list;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for(int i=1;i<=tc;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            arr = new int[n][n];
            list = new ArrayList<>();
            int max = 0;
            for(int j=0;j<n;j++) {
                st = new StringTokenizer(br.readLine());
                for(int k=0;k<n;k++) {
                    int temp = Integer.parseInt(st.nextToken());
                    arr[j][k] = temp;
                    // Max 값이 갱신될 경우 list를 초기화 하고 출발지를 넣어준다.
                    if(temp>max) {
                        list.clear();
                        list.add(new Pair(j,k,0,false,0));
                        max = temp;
                        // Max가 같을 경우 출발지에 넣어준다.
                    }else if(temp==max) list.add(new Pair(j,k,0,false,0));
                }
            }
            result = 0;
            visited = new boolean[n][n];
            for(int j=0;j<list.size();j++)
                solve(new Pair(list.get(j).x,list.get(j).y,1,false,0));
            System.out.println("#"+i+" "+result);
        }
    }
    
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    static boolean[][] visited;
    static int result;
    private static void solve(Pair t) {
        result = Math.max(result, t.cnt);
        visited[t.x][t.y] = true;
        for(int i=0;i<4;i++) {
            int tx = t.x+dir[i][0];
            int ty = t.y+dir[i][1];
            if(tx<0 || ty<0 || tx>=n || ty>=n) continue;
            if(visited[tx][ty]) continue;
            // tempK를 통해 이전에 파괴를 했다면 그 파괴된 값을 얻는다.
            if(arr[t.x][t.y]-t.tempK > arr[tx][ty]) {
                solve(new Pair(tx,ty,t.cnt+1,t.use,0));
            }else if(!t.use) {
                // 기회가 사용되지 않았다면
                // K 이하로 파괴가 가능 
                for(int j=1;j<=k;j++) {
                    if(arr[t.x][t.y] > arr[tx][ty] - j) {
                        solve(new Pair(tx,ty,t.cnt+1,true,j));
                        // 가장 작게 파괴해야 그 숫자가 큰 숫자가 된다.
                        break;
                    }
                }
            }
        }
        // 다음 탐색을 할 때 해당 index를 지나가야하므로 초기화
        visited[t.x][t.y] = false;
    }
    
    static class Pair{
        private int x;
        private int y;
        private int cnt,tempK;
        private boolean use;
        public Pair(int x,int y,int cnt,boolean use,int tempK) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.use = use;
            this.tempK = tempK;
        }
    }
}