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

문제

SW Expert Academy

 

풀이

0. 문제 해석

등산로의 규칙을 잘 이해하고 DFS를 진행해야 한다.

 

1. 가장 높은 봉우리에서 시작
2. 대각선 이동 불가, 자기보다 낮은 지형으로만 이동 가능
3. 한 지형 최대 K만큼 깎기 가능

 

여기서 문제에 언급되지 않은 정보가 있는데, 1번을 가장 먼저 해야한다.

만약 3번 규칙으로 하나의 산을 깎았는데 그게 최고점이라면 거기 또한 시작점이 되어야하는데 그 경우는 고려하지 않는 것 같다.

 

그리고 3번 규칙에서 "최대" K만큼 이라는 조건을 잘 봐야 한다. K만큼 깎는것이 아닌 0~K만큼 깎는 것이다.

 

그래서 문제를 풀기 위해 최고점을 찾아 그 최고점들에서 상하좌우 DFS를 진행하며,

경사가 더 높은 지형을 만났다면 1회에 한해 1~K만큼 깎아서 이동할 수 있는 경우 이동시킨다.

여기서 또한 왔던 길을 깎음으로써 다시 돌아갈수도 있으므로 그 경우를 피하기 위해 방문한 곳마다 방문 처리를 해준다.

 

 

1. 지도 입력

지도를 입력받으면서

가장 높은 봉우리의 값을 따로 체크한다.

 

2. DFS

가장 높은 봉우리들에서 DFS를 시작한다.

 

등산로 길이를 나타내기 위한 count, 한번 깎을 수 있는 기회를 표시하는 cut를 사용한다.

경사가 더 낮은 지형이라면 DFS를 진행하고

더 높은 지형이라면 한번도 깎지 않은 경우에 한해 1~k 만큼 깎아본다.

 

 

3. 전체 코드

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

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

public class Solution{
	static int n; // 한 변의 길이
	static int k; // 최대 공사 가능 깊이
	static int high; // 가장 높은 봉우리 (시작점)
	static int max; // 가장 긴 등산로의 길이
	static int[][] arr; // 지도 정보
	static int[][] visit; // 방문 정보
	// 상하좌우
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static StringTokenizer st;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
       
        for(int x = 1; x <= t; x++) {
        	max = 0;
        	high = 0;
        	
        	st = new StringTokenizer(br.readLine());
        	
        	n = Integer.parseInt(st.nextToken());
        	k = Integer.parseInt(st.nextToken());
        	
        	arr = new int[n + 2][n + 2];
        	visit = new int[n + 2][n + 2];
        	
        	// 지도 입력
        	for(int i = 1; i <= n; i++) {
        		st = new StringTokenizer(br.readLine());
        		for(int j = 1; j <= n; j++) {
        			arr[i][j] = Integer.parseInt(st.nextToken());
        			high = Math.max(high, arr[i][j]); // 가장 높은 봉우리 체크
        		}
        	}
        	
        	// 최고점에서 시작
        	for(int i = 1; i <= n; i++) {
        		for(int j = 1; j <= n; j++) {
        			if(arr[i][j] == high) {
        				visit[i][j] = 1;
        				dfs(i,j,1,1);
        				visit[i][j] = 0;
        			}
        		}
        	}
        	

        	System.out.println("#" + x + " "+ max);
        }
    }
    
    public static void dfs(int x,int y,int count, int cut) {
        int cur = arr[x][y];
 
        for(int i = 0; i < 4; i++) {
            int next = arr[x + dx[i]][y + dy[i]];
            // 외곽이 아니고 방문하지 않았다면
            if(next != 0 && visit[x + dx[i]][y + dy[i]] == 0) {
            	// 경사가 더 낮다면
		        if(next < cur) {
		        	visit[x + dx[i]][y + dy[i]] = 1;
		            dfs(x + dx[i], y + dy[i], count + 1,cut);
		            visit[x + dx[i]][y + dy[i]] = 0;
		        }
		        // 깎아서 갈 수 있는 길이고, 한번도 깎지 않았다면 깎아서 탐색
		        else if(cut == 1) {
		        	for(int j = 1; j <= k; j++) {
			        	if((next - j) < cur){
				        	arr[x + dx[i]][y + dy[i]] -= j;
				        	dfs(x + dx[i], y + dy[i], count + 1,cut - 1);
				        	arr[x + dx[i]][y + dy[i]] += j;
				        }
		        	}
		        } 
            }
        }
         
        if(count > max) {
            max = count;
        }
    }
 
}