[ 백준 2842 ] 집배원 한상덕

1. 문제: https://www.acmicpc.net/problem/2842

2842번: 집배원 한상덕

 

2. 풀이

문제의 핵심 조건은 아래와 같다.

 

1) 상하좌우 뿐만 아니라 대각선으로도 움직일 수 있다.

 

2) 방문하는 장소들 중 고도의 최고점과 최저점의 차이를 '피로도'라고 하며 이를 최소화 해야한다.

 

대각선을 추가하는 것이야 방향을 설정해주는 dy, dx 배열만 추가로 설정해주면 되는데 피로도를 최소화하기 위해서는 어떤 방법을 써야할 것 인가?

 

지도에서 주어진 모든 고도를 '중복 없이 정렬'한 뒤 low와 high를 설정해 해당 범위에 속하는 장소로만 이동하는 방식을 채택하면 된다.

 

모든 집에 우편을 배달했는지는 BFS로, 범위 값은 투 포인터 알고리즘으로 지정하고 시뮬레이션을 진행하였다.

 

BFS로 탐색함에 있어서 한 가지 중요한 점?은 시작점인 우체국도 low와 high 값 사이에 있어야 한다는 것이다. 이 부분에 대한 처리를 해주지 않았다가 무수한 '틀렸습니다'를 받아버렸다..ㅠ

 

3. 코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Postman2842 {
	static int N, house = 0;
	static int dy[] = {-1, 0, 1, 0, 1, 1, -1, -1};
	static int dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
	static int alti[][];
	static char map[][];
	static boolean visit[][];
	static ArrayList<Integer> list = new ArrayList<Integer>();
	static Point P; //우체국
	
	static boolean bfs(int lo, int hi) {
		//시작점 역시 지정한 저점과 고점의 범위에 속하는지 파악해야 함
        if(alti[P.y][P.x] < lo || alti[P.y][P.x] > hi) return;
        
       	for(int i = 0; i < N; i++) {
        	Arrays.fill(visit[i], false);
        }
        
		Queue<Point> q = new LinkedList<Point>();
		visit[P.y][P.x] = true;
		q.add(P);
		
        //집을 방문하는 횟수
        int cnt = 0;
		while(!q.isEmpty()) {
			Point now = q.poll();
            if(map[now.y][now.x] == 'K')
            	cnt++;
			for(int dir = 0; dir<8; dir++) {
				int ny = now.y + dy[dir];
				int nx = now.x + dx[dir];
				if(ny < 0 || nx < 0 || ny >= N || nx >= N || visit[ny][nx] || alti[ny][nx] < lo || alti[ny][nx] > hi) continue;
				visit[ny][nx] = true;
				q.add(new Point(ny, nx));
			}
		}
        
        if(cnt == house)
        	return true;
        return false;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];
		visit = new boolean[N][N];
		alti = new int[N][N];
        
        //지도 입력부
		for(int i = 0; i<N; i++) {
			String s = br.readLine();
			for(int j = 0; j<N; j++) {
				map[i][j] = s.charAt(j);
				if(map[i][j] == 'P')
					P = new Point(i, j);
				else if(map[i][j] == 'K')
					house++;
			}
		}
        
        //고도 입력부
		for(int i = 0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j<N; j++) {
				alti[i][j] = Integer.parseInt(st.nextToken());
				if(!list.contains(alti[i][j]))
					list.add(alti[i][j]);
			}
		}
		Collections.sort(list);
        
		int ans = Integer.MAX_VALUE, left = 0, right = 0;
		while(right != list.size()) {
			while(left != list.size()) {
				int lo = list.get(left);
				int hi = list.get(right);
				if(!bfs(lo, hi)) break;
				
				ans = Math.min(ans, hi - lo);
				left++;
			}
			right++;
		}

		bw.write(String.valueOf(ans));
		bw.flush();
		bw.close();
		br.close();
	}
	
	static class Point {
		int y;
		int x;
		public Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
}