1949번 : 등산로 조성 [Java]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

SW Expert Academy

 

해결 방안

1. 가장 높은 봉우리를 찾고, 가장 높은 봉우리에서 각각 탐색을 시작한다.

2. 현재 칸에서 인접한 낮은 칸으로 이동한다.

3. 낮지 않은 칸이라면, 높이 차이가 최대 공사 가능 깊이보다 작고 깎을 수 있는 상태라면 이동한다.

4. 최대 등산로 길이를 비교하며 저장한다.

 

 

주의할 점

1. 이미 등산로에 포함 된 칸은 깎으면 안된다. -> 따로 배열을 통해 관리

2. 탐색이 끝난후에는 원래대로 돌려놓는다.

 

 

전체 코드

import java.util.Scanner;

public class Solution {
	static int N, K;
	static int[][] map;
	static int[][] check;
	static int ans;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt(); // 지도의 한 변의 길이
			K = sc.nextInt(); // 최대 공사 가능 깊이
			map = new int[N][N];
			int Max = 0;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
					Max = Math.max(Max, map[i][j]);
				}
			}

			check = new int[N][N];
			ans = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == Max) {
						check[i][j] = 1;
						search(i, j, Max, 0, 1);
						check[i][j] = 0;
					}
				}
			}

			System.out.println("#" + tc + " " + ans);
		}
	}

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	private static void search(int i, int j, int cur, int cnt, int len) {
		ans = Math.max(ans, len);

		for (int d = 0; d < 4; d++) {

			int nx = i + dx[d];
			int ny = j + dy[d];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N)
				continue;
			if (check[nx][ny] == 1)
				continue;

			if (map[nx][ny] < cur) {
				check[nx][ny] = 1;
				search(nx, ny, map[nx][ny], cnt, len + 1);
				check[nx][ny] = 0;
			} else {
				if (cnt == 0) {
					if (map[nx][ny] - K < cur) {
						check[nx][ny] = 1;
						search(nx, ny, cur - 1, cnt + 1, len + 1);
						check[nx][ny] = 0;
					}
				}
			}
		}
	}
}