[JAVA/투포인터] 백준 2842 집배원 한상덕

1. 문제

https://www.acmicpc.net/problem/2842

2842번: 집배원 한상덕

 

2. 풀이

투포인터와 BFS를 모두 활용한다. 

1.  구해야 되는 것은 가장 작은 고도의 차이므로, 가장 높은 고도(high)와 가장 낮은 고도(low)를 설정해 그 고도 내에서 집배원이 모든 집을 방문할 수 있는지 본다. 투포인터를 이용해 low 값 과 high 값을 변경해가며 가장 작은 고도차를 찾는다.
2. 고도 내에서 모든 집을 방문할수 있는지 확인 할 때 BFS를 사용한다. BFS로 지도를 이동하면서 방문한 집의 개수를 확인한다.

 

3. 코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_2842 {
    
    static char[][] map; // 위치 저장
    static int n, pX, pY; // 우체국 위치
    static int[][] pirodo; // 피로도
    static int hCnt; // 집 개수
    static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
    
    // 범위 내에 있는지 확인
    public static boolean isInRange(int x, int y) {
        if(x < 0 || x >= n || y < 0 || y >= n) return false;
        return true;
    }
    
    // low ~ high의 피로도 사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
    public static int bfs(int low, int high) {
        int houseCnt = 0;
        
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        if(pirodo[pX][pY] < low || pirodo[pX][pY] > high) 
            return -1;
        
        q.add(new int[] {pX, pY});
        visited[pX][pY] = true;
        
        while(!q.isEmpty() && houseCnt < hCnt) {
            int[] nowPos = q.poll();
            
            for(int i = 0; i < 8; i++) {
                int newX = nowPos[0] + dir[i][0];
                int newY = nowPos[1] + dir[i][1];
                if(!isInRange(newX, newY) || visited[newX][newY]) continue;
                if(pirodo[newX][newY] < low || pirodo[newX][newY] > high) continue;
                
                visited[newX][newY] = true;
                q.add(new int[] {newX, newY});
                
                if(map[newX][newY] == 'K')
                    houseCnt++;
            }
        }
        
        return houseCnt;
    }

    public static void main(String[] args) throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        map = new char[n][n];
        pirodo = new int[n][n];
        
        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            map[i] = s.toCharArray();
            for(int j = 0; j < n; j++) {
                if(s.charAt(j) == 'P') {
                    pX = i; pY = j;
                }else if(s.charAt(j) == 'K') {
                    hCnt++;
                }
            }
        }
        
        ArrayList<Integer> hList = new ArrayList<Integer>();
        
        StringTokenizer st;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                pirodo[i][j] = Integer.parseInt(st.nextToken());
                hList.add(pirodo[i][j]);
            }
        }
        
        // 투포인터로 낮은 높이, 높은 높이를 지정해 그 높이 안에서 모든 집에 배달 할 수 있는지를 확인
        // 모든 집에 배달 할 수 있으면 정답 
        Collections.sort(hList);
        int answer = hList.get(hList.size() - 1) - hList.get(0); // max
        int low = 0, high = 0;
        while(low <= high && low < hList.size() && high < hList.size()) {
            
            // 낮은 높이, 높은 높이를 지정해 그 높이 안에서 모든 집에 배달 할 수 있는지를 확인 --> bfs
            if(bfs(hList.get(low), hList.get(high)) == hCnt) {
                int tmp = hList.get(high) - hList.get(low);
                if(tmp < answer) answer = tmp;
                low++;
            }else {
                high++;
            }
        }
        
        System.out.println(answer);
    }

}