[SWEA 1949] 등산로 조성 (Java)

SWEA 1949 등산로 조성

문제풀이

맵의 최대 크기가 8이다. 그리고 이 문제는 삼성 스타일이다. 완전탐색!

그런데... 완전탐색을 하려면 반복문이 엄청나게 중첩되는데 되는건가...?

• 높이를 낮출 지점 하나 찾기
  • 맵에서 가장 높은 높이 찾기
  • 가장 높은 지점에서 DFS

맵의 최대 크기 8, 최대로 낮출 수 있는 높이 5일 때를 상정하여

64 x 5(모든 위치에서 높이를 1 ~ 5 낮춰본다.) x 64(모든 지점에서 DFS를 수행해본다.) x 64(DFS 탐색이 맵 전체를 탐색한다.) = 1,310,720 최악의 경우에도 굉장히 작다. 완전탐색 가능하다!

예전에는 이 문제 푸는데 엄청 오래걸렸던 것 같은데 30분만에 풀어냈다. 뿌듯..

구현코드

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

public class Solution {
	
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static boolean[][] visited;
	static int[][] map;
	static int T, N, K, ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		for(int i = 1 ; i <= T ; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
		
			map = new int[N][N];
			visited = new boolean[N][N];
			ans = 0;
			
			for(int r = 0 ; r < N ; ++r) {
				st = new StringTokenizer(br.readLine());
				for(int c = 0 ; c < N ; ++c) {
					map[r][c] = Integer.parseInt(st.nextToken());
				}
			}
			
			for(int r = 0 ; r < N ; ++r) {
				for(int c = 0 ; c < N ; ++c) {
					for(int k = 1 ; k <= K ; ++k) {
						 map[r][c] -= k;
						 int height = findHighest();
						 findRoad(height);
						 map[r][c] += k;
					}
				}
			}
			
			System.out.println("#" + i + " " + ans);
		}
	
	}

	private static int findHighest() {
		int highest = 0;
		
		for(int r = 0 ; r < N ; ++r) {
			for(int c = 0 ; c < N ; ++c) {
				highest = map[r][c] > highest ? map[r][c] : highest;
			}
		}
		
		return highest;
	}

	private static void findRoad(int height) {
		for(int r = 0 ; r < N ; ++r) {
			for(int c = 0 ; c < N ; ++c) {
				if(map[r][c] == height) {
					init();
					dfs(r, c, 1);
				}
			}
		}
	}

	private static void dfs(int r, int c, int length) {
		ans = length > ans ? length : ans;
		
		for(int d = 0 ; d < 4 ; ++d) {
			int nr = r + dir[d][0];
			int nc = c + dir[d][1];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc]) continue;
			if(map[nr][nc] < map[r][c]) {
				visited[nr][nc] = true;
				dfs(nr, nc, length + 1);
				visited[nr][nc] = false;
			}
		}
	}
	
	private static void init() {
		for(int r = 0 ; r < N ; ++r) {
			for(int c = 0 ; c < N ; ++c) {
				visited[r][c] = false;
			}
		}
	}
}