[SWEA] 1949. 등산로 조성

문제

1949. [모의 SW 역량테스트] 등산로 조성
제일 긴 등산로의 길이를 반환하라!

• 높이 : [1, 20]
• 가장 높은 곳들에서 시작
• 현재 높이보다 작은 높이로만 이동 가능
• 한 번 최대 K깊이만큼 산을 깎을 수 있음 (⭐️ 깎았을 때 높이가 0이 되는 것은 허용)

풀이

가장 높은 지형들에서 DFS()를 호출하여 가장 긴 등산로를 찾는다.

if (map[nx][ny] < start.h) { // 현재보다 낮은 곳
	DFS(new Pair(nx, ny, map[nx][ny]), isCutted, length+1);
}
else { // 산을 깎을 수 있는가?
	if (isCutted == false && (map[nx][ny]-start.h)<k)
    			DFS(new Pair(nx, ny, start.h-1), true, length+1);
}

• DFS로 구현했다.
• 좌표를 기록할 Pair 클래스를 구현했다.
  • 산을 깎았을 때 map[][] 의 값을 바꾸지 않기 위해서 현재 높이를 기록한다.
• 재귀호출할 때 산을 깎았는지 여부(isCutted)를 넘겨주었다.
  • 다음 지형이 현재보다 지형이 높다면, 아직 깎지 않았고(isCutted==false) 깎을 높이가 k보다 작을 때 산을 깎고 이동할 수 있다. (-> isCutted를 true로 넘겨줌)
• 재귀호출하면 다른 지형으로 이동한 것이므로 length값을 1 올려준다.
• 다음 지형이 현재보다 높고, 산도 깎을 수 없으면 되돌아가서 다음 곳을 찾으므로 백트래킹이다.

자바코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{	
	static class Pair {
		int x;
		int y;
		int h; // height
		Pair() {}
		Pair(int x, int y, int h) {this.x=x; this.y=y; this.h=h;}
	}
	
	static int k=0;
	static int n=0;
	static int [][] map = new int[8][8];
	static boolean [][] isVisited = new boolean [8][8];
	
	static int maxLength = 0;
	
	static int [] dx = {-1, 0, 1, 0};
	static int [] dy = {0, -1, 0, 1};
	
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt(); 
		
		for(int test_case = 1; test_case <= T; test_case++)
		{				
			n = sc.nextInt();
			k = sc.nextInt();
			
			int max=0;
			map = new int[n][n];
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					// Load map
					map[i][j] = sc.nextInt();
					if (map[i][j] > max) max = map[i][j];
					
					// init visited
					isVisited[i][j] = false;
				}
			}
			
			// 가장 높은곳에서부터 등산로 탐색 
			maxLength = 0;
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					if (map[i][j] == max) {
						DFS(new Pair(i, j, map[i][j]), false, 1);
					}
				}
			}
 			
			System.out.printf("#%d %d\n", test_case, maxLength);
		}
	}
	

	static void DFS(Pair start, boolean isCutted, int length) {
		int nx, ny;
		isVisited[start.x][start.y] = true;
		if (length > maxLength) maxLength = length;
		
		for (int d=0; d<4; d++) {
			nx = start.x+dx[d];
			ny = start.y+dy[d];
			
            		// 영역 밖 또는 이미방문
			if(nx<0||nx>=n||ny<0||ny>=n||isVisited[nx][ny]) continue; 
			
			isVisited[nx][ny] = true;
			
			if (map[nx][ny] < start.h) { // 현재보다 낮은 곳
				DFS(new Pair(nx, ny, map[nx][ny]), isCutted, length+1);
			}
			else { // 산을 깎을 수 있는가?
				if (isCutted == false && (map[nx][ny]-start.h)<k)
                			DFS(new Pair(nx, ny, start.h-1), true, length+1);
			}
			
			isVisited[nx][ny] = false;
		}
		
		isVisited[start.x][start.y] = false;
		
	}
}

틀렸던 부분

• DFS에서 다음 지형이 영역 밖으로 나갔는 지 확인할 때, nx<=0 으로 했었다..ㅎ ! !
• 깎았을 때도 높이가 1 이상이어야 되는 줄 알았다. (문제를 잘 읽자^^)