[SWEA/1949/JAVA] 등산로 조성

DFS

 

문제 요약

1. 2차원 배열에서 가장 긴 등산로 만들기
2. 규칙
   • 가장 높은 봉우리에서 시작
   • 4방 탐색
   • 높은곳에서 낮은곳으로만 이동 가능 (같은 곳X)
   • 딱 한번 최대 K만큼 높이를 깎을 수 있음

 

풀이

1. 최대지점(봉우리)부터 dfs
2. 직전 높이보다 낮으면 dfs, 같거나 높으면 높이를 깎은적이 없는 경우에만 최대 K만큼 깎아서 이동할 수 있는지 확인해서 dfs

 

비고

• 풀이 자체는 금방 떠올랐으나 예외 잡는 데에 오래 걸림 ㅠㅠ

 

 

package s01.SWEA_1949_등산로조성;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, K, answer, map[][];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		int T = Integer.parseInt(br.readLine());
		StringBuilder result = new StringBuilder();

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			answer = 0;

			map = new int[N][N];

			int max = 0;

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

			for (int r = 0; r < N; r++) {
				for (int c = 0; c < N; c++) {
					if (map[r][c] == max) {
						boolean[][] visit = new boolean[N][N];
						visit[r][c] = true;
						dfs(r, c, 1, map[r][c], false, visit);
					}
				}
			}
			result.append("#" + tc + " " + answer + "\n");
		}
		System.out.println(result);
	}

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	private static void dfs(int r, int c, int depth, int height, boolean use, boolean[][] visit) {
		boolean isEnd = true;
		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];

			if (!check(nr, nc) || visit[nr][nc])
				continue;

			visit[nr][nc] = true;
			if (height > map[nr][nc]) {
				dfs(nr, nc, depth + 1, map[nr][nc], use, visit);
				isEnd = false;
			} else if (!use && map[nr][nc] - map[r][c] + 1 <= K) {
				dfs(nr, nc, depth + 1, map[r][c] - 1, true, visit);
				isEnd = false;
			}
			visit[nr][nc] = false;
		}

		if (isEnd) {
			answer = Math.max(answer, depth);
		}
	}

	private static boolean check(int r, int c) {
		if (r >= 0 && r < N && c >= 0 && c < N)
			return true;
		return false;
	}

}

 

 

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

SW Expert Academy