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

[제약 사항]

1. 시간 제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초

2. 지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)

3. 최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)

4. 지도에 나타나는 지형의 높이는 1 이상 20 이하의 정수이다.

5. 지도에서 가장 높은 봉우리는 최대 5개이다.

6. 지형은 정수 단위로만 깎을 수 있다.

7. 필요한 경우 지형을 깎아 높이를 1보다 작게 만드는 것도 가능하다.

이 문제에서 주목해야 할 점은 "지도의 한 변의 길이 N은 3이상 8이하의 정수이다." 와

"최대 공사 가능 깊이 K는 1이상 5이하의 정수이다." 이다.

이 점을 가지고 생각해보면

가장 큰 지도 인 8 x 8에서 64가지 경우를 여기서 K만큼 깍는데 0~5가 된다.( 최대 공사 가능 깊이기 때문에 깍지 않는 경우도 포함된다.)

따라서 64 x 6 이라는 최대의 경우의 수 가 나오고

bfs를 진행하더라도 무리가 없다는 점에서 착안을 하였다.

먼저 입력을 받으면서 이 지도에서 최대 높이가 몇인지 확인 한 후에

다시 이중 for문을 통하여 가장 높은 봉우리가 되는 지점을 ArrayList에 저장 하였고

1 .ArrayList에서 한 점씩 뽑아내고 

2. 몇 K를 낮출 지 정하고

3. 낮출 좌표를 찾아내어 ( 단, 낮출 지점을 지금 당장 출발할 가장 높은 봉우리는 제외시켰다. )

4. 메소드를 호출하여 사용하였다.

이 부분의 코드는 다음 과 같고 메소드에서는 일반적인 bfs를 사용하였다.

for(int i=0; i<N; i++) {
    s = br.readLine().split(" ");
    for(int j=0; j<N; j++) {
        arr[i][j] = Integer.parseInt(s[j]);
        if( arr[i][j] > max ) max = arr[i][j];
    }
}
ArrayList<Node> list = new ArrayList<>();
            
for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
        if(arr[i][j] == max) list.add(new Node(i, j, 0));
    }
}
            
for(Node node : list) {
 
    for(int k=K; k>=0; k++) {
 
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
    
                if( node.i == i && node.j == j) continue;
    
                climbing(node.i, node.j, k, i, j);
            }
        }
    }
}

전체 코드는 다음과 같다.

package swexpertacademy;
 
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution1949 {
    static int[][] arr;
    static int N;
    static int K;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int result;
    
    static class Node{
        int i, j, cnt;
        Node(int i, int j, int cnt){
            this.i = i;
            this.j = j;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        String[] s = null;
        for(int t=1; t<=T; t++) {
            s = br.readLine().split(" ");
            N = Integer.parseInt(s[0]);
            K = Integer.parseInt(s[1]);
            arr = new int[N][N];
            int max = 0;
            result = 0;
            for(int i=0; i<N; i++) {
                s = br.readLine().split(" ");
                for(int j=0; j<N; j++) {
                    arr[i][j] = Integer.parseInt(s[j]);
                    if( arr[i][j] > max ) max = arr[i][j];
                }
            }
            ArrayList<Node> list = new ArrayList<>();
            
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(arr[i][j] == max) list.add(new Node(i, j, 0));
                }
            }
            
            for(Node node : list) {
                for(int k=K; k>=0; k++) {
                    for(int i=0; i<N; i++) {
                        for(int j=0; j<N; j++) {
                            if( node.i == i && node.j == j) continue;
                            climbing(node.i, node.j, k, i, j);
                        }
                    }
                }
            }
            
            bw.write("#"+t+" "+result+"\n");
        }
        br.close();
        bw.close();
    }
    
    
    static void climbing(int q, int w, int k, int x, int y) {
        arr[q][w] -= k;
        Queue<Node> qu = new LinkedList<>();
        qu.offer(new Node(x, y, 1));
        Node node = null;
        int ni = 0;
        int nj = 0;
        while(!qu.isEmpty()) {
            node = qu.poll();
            if(node.cnt > result) result = node.cnt;
            for(int i=0; i<4; i++) {
                ni = node.i + dx[i];
                nj = node.j + dy[i];
                if( ni < 0 || nj < 0 || ni > N-1 || nj > N-1 ) continue;
                if( arr[ni][nj] < arr[node.i][node.j]) qu.offer(new Node(ni, nj, node.cnt+1));
            }
        }
        arr[q][w] += k;
    }
}