주의할 점 2번을 깨닫는게 좀 어려웠던것 같다.
한상덕의 피로도는 전체 경로중에 가장 높은 고도와 가장 낮은 고도의 차이이며 이를 최소화하는것이 이 문제의 목표이다.
즉, DFS로 한상덕의 마을을 탐색한다고 했을때, 부분적인 경로에서 피로도를 최소화하는것으로는 문제해결이 불가능하다는 것 이다.
따라서 전체 경로에 대한 가장 낮은고도와 가장 높은 고도를 설정해 놓고, 이 고도사이에서 모든 집을 방문할 수 있는가를 확인하는것이 풀이방법이 될 것 이다.
1. 전체 경로의 고도 특정하기
입력을 통해 마을의 모든 부분의 고도를 확인할 수 있는데 이를 중복을 제거하고 오름차순으로 정렬한다.
이 정렬된 고도값들에 두개의 포인터(left, right 등)를 사용하여 고도값을 조정한다.
while(left <= right && right < 고도값개수){
...//left와 right이용해 최대, 최소 고도를 우체국에서 출발하는 dfs에 전달하기
if(dfs결과방문한집개수 == 전체집개수){
right = Math.min(result, altitute[right] - altitute[left]);
left++;
}else right++;
}
2. DFS 구현하기
DFS메서드의 인자는 최대고도, 최소고도, 현재위치를 가지도록 했고,
리턴값은 해당 부분경로에서 방문한 집의 개수로 했다.
int dfs(int low, int high, int h, int w){
//1. 기저조건(이미 방문했거나 지도의 범위를 벗어난경우 0리턴)
//2. 탐색하기(갈 수 있는 부분경로들의 결과값을 모두 합침)
//3. 리턴
}
import java.io.*;
import java.util.*;
public class 집배원_한상덕 {
//https://www.acmicpc.net/problem/2842
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
board = new char[N][];
altitute = new int[N][N];
//중복을 제거하기위해 Set사용함
HashSet<Integer> alts = new HashSet<Integer>();
for(int h = 0; h < N; h++){
board[h] = br.readLine().toCharArray();
for(int w = 0; w < N; w++){
if(board[h][w] == 'P'){ph = h; pw = w;}
else if(board[h][w] == 'K'){K++;}
}
}
for(int h = 0; h < N; h++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int w = 0; w < N; w++){
altitute[h][w] = Integer.parseInt(st.nextToken());
alts.add(altitute[h][w]);
}
}
System.out.println(find(alts));
}
static int find(HashSet<Integer> alts){
int result = 1000000;
Integer[] alt = alts.toArray(new Integer[0]);
Arrays.sort(alt);
int low = 0, high = 0;
int right = 0, left = 0;
while(left <= right && right < alt.length){
low = alt[left]; high = alt[right];
vis = new boolean[N][N];
int visitedHomes = dfs(low, high, ph, pw);
if(visitedHomes == K){
result = Math.min(result, high - low);
left++;
}else right++;
}
return result;
}
static int N, K = 0;
static int ph = 0, pw = 0;
static char[][] board;
static int[][] altitute;
static int[] alt;
static boolean[][] vis;
static int[][] dir = {
{0, 1},
{1, 1},
{1, 0},
{1, -1},
{0, -1},
{-1, -1},
{-1, 0},
{-1, 1}
};
//정해진 low, high로 전체 집을 탐색할 수 있는가?
static int dfs(int low, int high, int h, int w){
if(high < low || h < 0 || h >= N || w < 0 || w >= N || vis[h][w] || low > altitute[h][w] || high < altitute[h][w]) return 0;
vis[h][w] = true;
int result = 0;
if(board[h][w] == 'K') result++;
for(int d = 0; d < dir.length; d++) result += dfs(low, high, h + dir[d][0], w + dir[d][1]);
return result;
}
}