[SWEA] 1949. [모의 SW 역량테스트] 등산로 조성(자바/DFS)

문제 조건

 

문제 접근

1. 가장 높은 봉우리에서 시작해야 한다

따라서, 가장 높은 봉우리들을 찾아 이에 대한 DFS 탐색을 모두 진행해야 한다.

 

2. 높은 지형에서 낮은 지형으로 연결되어야 한다.

따라서, 탐색할 지형(maps[nextX][nextY])이 현재 지형(maps[nowX][nowY])보다 크거나 같은 경우 지형을 깎아줘야 한다.   

하지만, 3번 조건에 따라 이전에 지형을 깍은 경우에는 지형을 깎을 수 없다

 

 3. 긴 등산로를 만들기 위해 딱 한 곳만 정할 수 있다.

따라서, boolean 변수를 선언하여 지형을 깍는 경우 true로 세팅하여 한 곳만 깎을 수 있게 조건을 준다.

 

4. DFS로 문제를 접근한 이유

만들 수 있는 가장 긴 등산로 길이를 구해야한다. DFS로 탐색하면 갈 수 있는 곳까지 끝까지 가볼 수 있으므로 DFS로 탐색을 진행하였다.

현재 좌표를 기준으로 상하좌우로 가보고 탐색해볼 수 있어야 하므로, int[][] dir 방향 배열을 선언하여 상하좌우로 가볼 수 있도록 구현하였다.

 

5. 지형 깍기

지형의 경우 최대 K만큼 깎아볼 수 있다. 최대한 등산로 길이가 길게 나올 수 있도록, 깎아야 하는 지형은 현재 지형에서 -1의 높이가 될 수 있어야 한다. 예를 들어 5 4 7 1의 경우 4->7의 경우 4->3(깎는 지형 : 4)이 되며, 이때 깍는 지형이 K보다 작으면 탐색을 진행한다.

//package swea.p1949;

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

/*
 * swea 1949. [모의 SW 역량테스트] 등산로 조성
 * */
public class Solution {

	static int N;
	static int K;
	static boolean[][] visited;
	static int[][] maps;
	static int result;

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

		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());

			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			maps = new int[N][N];
			result = Integer.MIN_VALUE;
			visited = new boolean[N][N];

			int max = Integer.MIN_VALUE;
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					maps[i][j] = Integer.parseInt(st.nextToken());
					max = Math.max(max, maps[i][j]);
				}
			}

			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (max == maps[i][j]) {//가장 높은 봉우리에서 dfs 시작
						solve(i, j, false, 1);
					}
				}
			}
			

			
			sb.append(String.format("#%d %d\n", tc, result));
		}
		System.out.println(sb);
	}

	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };// 상하좌우

	
	/**
	 * @param nowX
	 * @param nowY
	 * @param height 현재 위치의 높이
	 * @param flag 지형을 깍았는지 확인
	 */
	static void solve(int nowX, int nowY, boolean flag, int lengthCnt) {
		result = Math.max(result, lengthCnt);
		
		visited[nowX][nowY] = true;
		
	    for (int i = 0; i < dir.length; i++) {
	        int nextX = nowX + dir[i][0];
	        int nextY = nowY + dir[i][1];
	        
	        if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= N || visited[nextX][nextY]) continue;

	    
	        if(maps[nextX][nextY] < maps[nowX][nowY]) {//이동 가능한 높이
	        	solve(nextX, nextY, flag, lengthCnt+1);
	        }else if(!flag && maps[nextX][nextY] >= maps[nowX][nowY]) {//지형을 깍고, flag를 true
	        	int depth = (maps[nextX][nextY] - maps[nowX][nowY]) + 1;
                if(depth <= K){
                    int tmp = maps[nextX][nextY];
                    maps[nextX][nextY] = maps[nowX][nowY] - 1;//현재 지형 - 1 만큼만 깍으면 됨
                    solve(nextX, nextY, true, lengthCnt+1);
                    maps[nextX][nextY] = tmp;
                }
	        }
	    }
	    
	    visited[nowX][nowY] = false;
	}
	
	
}