[JAVA] 2842 집배원 한상덕

난이도

플래티넘5

 

알고리즘: 투 포인터, DFS/BFS

배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 하자.
이때, 가장 작은 피로도로 모든 집에 배달을 하려면 어떻게 해야 하는지 구하는 프로그램을 작성하시오.

 

이 문제에서는 경로 혹은 거리가 중요하지 않다. 가장 작은 피로도로 우체국과 모든 집을 방문할 수 있으면 된다. 따라서 가장 작은 피로도를 만드는 '가장 높은 곳'과 '가장 낮은 곳'을 구해야 한다. 최대 고도와 최소 고도를 정해야 한다는 것이다.

 

그렇다면 지도에 존재하는 모든 피로도를 탐색하며 최대 고도와 최소 고도를 정한 후, 해당 범위로 조건을 만족할 수 있는 지 검사하면 된다. 하지만, 이렇게 완전 탐색으로 문제를 풀면 굳이 시간 복잡도를 계산하지 않아도 시간이 초과될 것을 예측할 수 있다.

 

따라서 시간을 줄이기 위해 투 포인터를 생각할 수 있다. 가장 높은 곳과 가장 낮은 곳을 결정할 때, 각각 포인터를 이용해 범위를 바꾸는 것이다. 다만 어떠한 범위가 조건을 만족시켰다고 해도, 문제에서 '가장 작은' 피로도를 요구하기 때문에 탐색을 멈추면 안 된다.

sort(고도들)

while(bottom <= top):
    if(bfs(bottom, top) == true):
    	answer = min(answer, top - bottom 고도)
        포인터 조절
    else:
    	포인터 조절

그렇다면 포인터는 어디서 시작하고 어떻게 조절할까? 만약 우체국이나 집 중 하나의 고도에서 출발한다면, 즉 정렬된 고도들 중 중간 고도에서 출발하게 된다면 포인터 조절이 어려워진다. BFS 실행에 성공했을 때 혹은 실패했을 때 두 포인터 중 어느 쪽을 움직여야 할 지 정하기 어렵다.

 

따라서 맨 처음 또는 맨 뒤에서 포인터를 시작하고, BFS 성공 시 한 쪽 포인터를 움직여 피로도를 줄이고, 실패 시 다른 쪽 포인터를 움직여 피로도를 키우는 방법을 생각할 수 있다.

sort(고도들)

bottom = top = 0

while(bottom <= top):
    if(bfs(bottom, top) == true):
    	answer = min(answer, top - bottom 고도)
        bottom++
    else:
    	top++

DFS/BFS는 우체국에서 시작해 모든 집들에 방문을 완료하면 true를 반환하고, 완료하지 못하고 반환하면 false를 반환하게 한다. 모든 집들에 방문을 완료하고 다시 우체국으로 돌아오는 경로는 지금까지 지나온 경로로 돌아가면 되므로 따로 고려하지 않아도 된다.

 

따라서 최종 코드는 다음과 같다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class BOJ2842 {
    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static class Info {
        char type;
        int height;

        public Info(char type, int height) {
            this.type = type;
            this.height = height;
        }
    }

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb;

    static int N, homeCnt;
    static Info[][] map;
    static Point postOffice;

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

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();
        
        N = Integer.parseInt(br.readLine());
        map = new Info[N][N];
        homeCnt = 0;

        for (int r = 0; r < N; r++) {
            String row = br.readLine();
            for (int c = 0; c < N; c++) {
                map[r][c] = new Info(row.charAt(c), 0);
                if (map[r][c].type == 'K') {
                    homeCnt++;
                } else if (map[r][c].type == 'P') {
                    postOffice = new Point(r, c);
                }
            }
        }

        Set<Integer> heightSet = new TreeSet<>();

        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c].height = Integer.parseInt(st.nextToken());
                heightSet.add(map[r][c].height);
            }
        }

        List<Integer> heights = new ArrayList<>(heightSet);
        int minIdx = 0, maxIdx = 0;
        int answer = heights.get(heights.size() - 1) - heights.get(0);
        
        while (maxIdx < heights.size() && minIdx <= maxIdx) {
            int min = heights.get(minIdx);
            int max = heights.get(maxIdx);

            if (!bfs(min, max)) {
                maxIdx++;
            } else {
                answer = Math.min(answer, max - min);
                minIdx++;
            }
        }
        
        bw.write(sb.append(answer).append('\n').toString());
        bw.flush();
    }

    private static boolean bfs(int min, int max) {
        if (map[postOffice.r][postOffice.c].height < min
                || map[postOffice.r][postOffice.c].height > max)
            return false;

        boolean[][] isVisited = new boolean[N][N];
        isVisited[postOffice.r][postOffice.c] = true;
        
        Queue<Point> queue = new ArrayDeque<>();
        queue.add(postOffice);

        int currHomeCnt = 0;

        while (!queue.isEmpty()) {
            Point curr = queue.poll();
            if (currHomeCnt == homeCnt) {
                return true;
            }

            for (int dir = 0; dir < 8; dir++) {
                int nextR = curr.r + dr[dir];
                int nextC = curr.c + dc[dir];
                if (canMove(nextR, nextC) && !isVisited[nextR][nextC]
                        && map[nextR][nextC].height >= min 
                        && map[nextR][nextC].height <= max) {
                    
                    isVisited[nextR][nextC] = true;
                    if (map[nextR][nextC].type == 'K') {
                        currHomeCnt++;
                    }
                    queue.add(new Point(nextR, nextC));
                }
            }
        }
        
        return false;
    }

    private static boolean canMove(int r, int c) {
        return r >= 0 && c >= 0 && r < N && c < N;
    }

}