#백준_2842 집배원 한상덕 - Java 자바

# 유형 : 탐색, BFS, 투포인터

# 난이도 : 플래티넘 V

# 플래티넘 난이도 치고 그렇게 어렵지 않았다. 피로도 구간을 BFS + 투포인터를 이용하여 차이가 최소일 때를 찾으면 되는 문제였다. 

우선 피로도를 중복 없이 입력받으면서, 정렬을 한다. 그리고 나서 low, high 포인트를 지정하여 늘려가며 최소인 구간을 찾으면 되는 문제이다. 첫 번째 테스트케이스는 아래와 같이 진행된다. low~high 구간에 있는 땅만 밟으면서 이동시키면 된다.

3(index = 0)	4(index = 1)	5(index = 2)	7(index = 3)	8(index = 4)	9(index = 5)
low,high(초기)
low	high
low		high
low			high
low				high(집 all 방문)
	low			high
		low			high

 

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2842 {
    static int N, House, Min=999999;
    static Point start;
    static boolean visit[][];
    static char map[][];
    static int arr[][];
    static ArrayList<Integer> arrList = new ArrayList<>();
    static int moveX[] = {0,1,1,1,0,-1,-1,-1};
    static int moveY[] = {-1,-1,0,1,1,1,0,-1};
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        arr = new int[N][N];
        
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<N; j++) {
                char ch = str.charAt(j);
                
                if(ch == 'P')
                    start = new Point(j,i);
                if(ch == 'K')
                    House++;
                
                map[i][j] = ch;
            }
        }
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                int val = Integer.parseInt(st.nextToken());
                arr[i][j] = val;
                if(!arrList.contains(val))
                    arrList.add(val);
            }
        }
        Collections.sort(arrList);
        
        bfs();
        
    }
    public static void bfs() {
        int low=0, high=0;
        while(low<arrList.size()) {
            visit = new boolean[N][N];
            Queue<Point> queue = new LinkedList<Point>();
            int val = arr[start.y][start.x];
            if(arrList.get(low)<= val && val<=arrList.get(high)) {
                visit[start.y][start.x] = true;
                queue.add(new Point(start.x, start.y));
                
            }
            int count = 0;
            while(!queue.isEmpty()) {
                Point po = queue.poll();
                if(map[po.y][po.x] == 'K') {
                    count++;
                }
                
                for(int d=0; d<8; d++) {
                    int newY = po.y + moveY[d];
                    int newX = po.x + moveX[d];
                    
                    if(0<=newY && newY<N && 0<=newX && newX<N && !visit[newY][newX]) {
                        int nextVal = arr[newY][newX];
                        if(arrList.get(low)<= nextVal && nextVal<=arrList.get(high)) {
                            visit[newY][newX] = true;
                            queue.add(new Point(newX,newY));
                        }
                    
                    }
                }
            }
            if(House == count) {
                Min = Math.min(Min, arrList.get(high) - arrList.get(low));
                low++;
            }else if(high + 1 < arrList.size()) {
                high++;
            }else
                break;
        }
        
        System.out.println(Min);
    }
}