[SWEA 1949 - Java] 등산로 조성

SW Expert Academy

 

풀이

이 문제의 경우엔 DFS 알고리즘을 이용해서 풀이하였습니다.

 

1. 가장 높은 봉우리들을 모두 큐에 저장한 뒤에 하나씩 뽑으면서 각각의 봉우리에서 시작하는 등산로들을 확인해야 합니다.
2. 이 과정에서 재귀를 이용한 DFS 알고리즘을 사용합니다.
   1. 상하좌우의 이동을 확인합니다. 범위가 벗어나거나 이미 방문한 지점의 경우엔 다시 방문 하지 않습니다.
   2. 이동하려는 곳의 높이가 더 낮은 경우엔 road+1과 이동한 위치를 가지고 dfs함수를 재귀 호출합니다.
   3. 이동하려는 곳의 높이가 현위치 이상인 경우가 중요합니다!
      
      1. 이 때는 k 이하로 깎아서 현위치의 높이 이하가 되며 아직 깎은 땅이 없는 경우만 그 위치로 등산로 건설이 가능합니다.
      2. 따라서 이러한 경우만 road+1과 이동한 위치, 땅을 이미 깎았다는 표시를 가지고 dfs함수를 재귀 호출합니다.
   4. road의 길이가 answer보다 커지게 되는 지를 매 재귀 시작에 확인하고 커지는 경우엔 answer값을 업데이트 합니다.
3. 모두 완료후 answer에 저장된 값을 출력하면 됩니다.

 

import java.util.Scanner;
import java.util.*;

public class Solution {

	static int N, K;
	static int[][] map;
	static int[][] visited;
	static int answer;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int i=0; i<T; i++) {
			N = sc.nextInt();
			K = sc.nextInt();
			map = new int[N][N];
			answer = 0;
			int maxH = 0;
			
			Queue<Pos> q = new LinkedList<>();
			
			for(int j=0; j<N; j++) {
				for(int l = 0; l<N; l++) {
					map[j][l] = sc.nextInt();
					
					if(map[j][l] == maxH) {
						q.add(new Pos(j, l));
						
					}
					
					else if(map[j][l] > maxH) {
						maxH = map[j][l];
						q.clear();
						q.add(new Pos(j, l));
					}
				}
			}
			
			while(!q.isEmpty()) {
				
				Pos top = q.poll();
				
				visited = new int[N][N];
				visited[top.r][top.c] = 1;
	
				dfs(1, top.r, top.c, false);
			}
			
			System.out.println("#"+(i+1)+" "+answer);
			
		}
	}
	
	static void dfs(int road, int nowR, int nowC, boolean cut) {
		
		if(road > answer)
			answer = road;
		
		int[] R = {1, -1, 0, 0};
		int[] C = {0, 0, 1, -1};
		
		
		
		for(int i=0; i<4; i++) {
			int nextR = nowR+R[i];
			int nextC = nowC+C[i];
			
			//System.out.println(nowR+" "+nowC+" "+road+" "+cut+" "+nextR+" "+nextC+" "+map[nowR][nowC]);
			
			if(nextR<0 || nextR>=N || nextC<0||nextC>=N)
				continue;
			
			if(visited[nextR][nextC] == 1)
				continue;
			
			//그냥 길 생성 가능 
			if (map[nowR][nowC] > map[nextR][nextC]) {
				visited[nextR][nextC] = 1;
				dfs(road+1, nextR, nextC, cut);
				visited[nextR][nextC]= 0;
			}
			
			// 깎아야함.
			else if(map[nowR][nowC] <= map[nextR][nextC] && cut == false) {
				int temp = map[nextR][nextC];
				
				if(map[nextR][nextC] - map[nowR][nowC] < K) {
					map[nextR][nextC] = map[nowR][nowC] - 1;
					visited[nextR][nextC] = 1;
					dfs(road+1, nextR, nextC, true);
					map[nextR][nextC] = temp;
					visited[nextR][nextC]= 0;
				}
			}
			
			
		}
		
	}
	
	
	static class Pos {
		int r, c;
		Pos(int r, int c){
			this.r = r;
			this.c = c;
			
		}
	}

}