[SWEA] 1949번 등산로 조성 (JAVA)

SW Expert Academy

기본적인 로직은

상, 하, 좌, 우를 탐색하여

 

이전 봉우리보다 낮은 경우

→ 한 칸 더 갈 수 있다.

 

이전 봉우리보다 높거나 같은 경우

→ 현재 봉우리의 높이를 1~K 만큼 깎아서

(이전 봉우리 높이 - 1) 로 만들 수 있는지 판단.

→만들 수 있으면 한 칸 더 갈 수 있다.

이때, 깎을 수 있는 기회는 한 번뿐이므로

깎았다고 표시를 해줘야 한다.

 

이렇게 가장 긴 길이를 찾는 문제이므로 DFS로 풀면 되지만

굳이 굳이 BFS로 접근해서 방문 체크 때문에 머리 아팠다.

 

DFS는 깊이 우선 탐색이기 때문에

방문 배열 한 개 가지고 재귀 호출을 통해

체크했다가 지웠다 할 수 있지만

 

BFS는 여러 개의 행적을 처리해야 해서

방문 배열 한 개로는 절대 체크할 수 없다.

그래서 큐에 값을 집어넣을 때,

방문 큐 라는 것도 만들어서

여기 오기 전까지 어딜 방문했는지를 체크해놓은

이차원 배열을 집어넣었다.

 

방문 큐에서 배열을 꺼낼 땐

임시 배열에 깊은 복사를 해준 뒤 사용해야 한다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SWEA_1949_등산로조성 {
	private static int T, N, K, max, res;
	private static int arr[][], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	private static Queue<int[]> q = new LinkedList<>();
	private static Queue<int[][]> visited = new LinkedList<>();
	
	public static void bfs() {
		while(!q.isEmpty()) {
			for(int i = 0; i < 4; i++) {
				int x = q.peek()[0] + dx[i], y = q.peek()[1] + dy[i], chk = q.peek()[2], depth = q.peek()[3], height = q.peek()[4];
				int tmp[][] = new int[N][N];
				for(int j = 0; j < N; j++) tmp[j] = visited.peek()[j].clone(); // 방문 배열 임시 배열에 깊은 복사
				
				if(x < 0 || x >= N || y < 0 || y >= N || tmp[x][y] == 1) continue; // 배열 범위를 벗어나거나 방문을 한 적이 있으면 넘어감
				
				if(arr[x][y] < height) { // 이전 높이 보다 작으면
					q.offer(new int[] {x, y, chk, depth + 1, arr[x][y]}); // 정상적으로 큐에 추가
				}
				else if(chk == 0 && K >= arr[x][y] - height + 1) { // 이전보다 같거나 큰데 깎은 적이 없고 깎을 수 있는 K 범위를 가졌다면
					q.offer(new int[] {x, y, 1, depth + 1, height - 1}); // 큐에 추가할 때 깎았다고 표시
				}
				else continue; // 그게 아니면 넘어감
				
				tmp[x][y] = 1; // 방문 체크
				visited.offer(tmp); // 방문 배열도 추가
			}
			res = Math.max(res, q.poll()[3]); // 큐 poll할 때마다 최대 길이 갱신
			visited.poll();
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for(int t = 1; t <= T; t++) {
			N = sc.nextInt(); K = sc.nextInt();
			arr = new int[N][N];
			max = 0; res = 1;
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
					max = Math.max(max, arr[i][j]); // 최대 높이 찾기
				}
			}
			
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(arr[i][j] == max) { // 최대 높이 산부터
						int tmp[][] = new int[N][N]; tmp[i][j] = 1; // 방문 배열 생성 후 체크
						q.offer(new int[] {i, j, 0, 1, arr[i][j]});
						visited.offer(tmp);
						bfs();
					}
				}
			}
			
			System.out.println("#" + t + " " + res);
		}
	}
}