백준 2842 집배원 한상덕 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/2842

2. 코드가 나오기까지 🛠️

1. 고도 값들을 중복 없이 저장해서 오름 차순 정렬한다. (set과 배열, sort 활용)

2. 정렬된 고도를 저장한 배열을 heights[]라고 할 때, 해당 배열에서 투 포인터를 운용한다.
   (왼쪽 포인터 L = 최소 고도, 오른쪽 포인터R= 최대 고도)
1. heights[L] ~ heights[R] 사이에 모든 집을 방문할 수 있다면 L을 한 칸 올려서 고도차를 줄여본다.
2. 모든 집을 방문할 수 없다면, R을 한 칸 올려서 고도차를 줄인다.
3. 위 계산에서 모든 집을 방문할 수 있을 때마다 최소 고도차를 기존 값과 현 고도차를 비교하여 더 작은 값으로 갱신한다.

(1) 시간복잡도 분석 ⏳

1. 투 포인터 = $$O(N^{2})$$

2. BFS = $$O(N^{2})$$

3. 코드 🌐

import java.util.*;
import java.io.*;

public class Main {
    static class Coordinate {
        int r;
        int c;

        public Coordinate(int r, int c){
            this.r = r;
            this.c = c;
        }    }    static int N, K;
    static int [][]  map;
    static int [] heights;
    static int [][] dir = new int [][]
        {{0,1},{0,-1},{1,0},{-1,0},
            {1,1},{1,-1},{-1,-1},{-1,1}};
    static Coordinate post_office;
    static boolean [][] homes;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        K = 0;
        map = new int [N][N];
        homes = new boolean [N][N];
        for(int i = 0; i < N; i++){
            String row = br.readLine();
            for(int j = 0; j < N; j++){
                char now = row.charAt(j);
                if(now == 'P') post_office = new Coordinate(i,j);
                if(now == 'K') {
                    homes[i][j] = true;
                    K++;
                }            }        }
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                set.add(map[i][j]);
            }        }        heights = new int [set.size()];
        int iter = 0;
        for(int temp : set){
            heights[iter++] = temp;
        }        Arrays.sort(heights);

        int left = 0;
        int right = 0;

        int min = Integer.MAX_VALUE;
        while(left < heights.length && right < heights.length){
            if(left > right) right++;
            boolean result = bfs(heights[left], heights[right]);
            if(result) {
                min = Math.min(min, heights[right] - heights[left]);
                left++;
            }else{
                right++;
            }        }        System.out.println(min);
    }
    public static boolean bfs (int low, int high){
        if(map[post_office.r][post_office.c] < low || map[post_office.r][post_office.c] > high) return false;
        int visit_cnt = 0;
        boolean [][] check = new boolean [N][N];
        ArrayDeque<Coordinate> aq = new ArrayDeque<>();
        aq.add(new Coordinate(post_office.r, post_office.c));
        check[post_office.r][post_office.c] = true;

        while(!aq.isEmpty()){
            Coordinate now = aq.poll();
            for(int i = 0; i < 8; i++){
                int nr = now.r + dir[i][0];
                int nc = now.c + dir[i][1];
                if(OOB(nr,nc) || check[nr][nc])  continue;
                if(map[nr][nc] < low || map[nr][nc] > high) continue;
                if(homes[nr][nc]) visit_cnt++;
                if(visit_cnt == K) return true;
                check[nr][nc] = true;
                aq.add(new Coordinate(nr,nc));
            }        }        return false;
    }
    public static boolean OOB (int r, int c) {
        return r < 0 || c < 0 || r >= N || c >= N;
    }
}

4. 트러블 슈팅 or 배운 점📝

• 풀이 참고: https://comyoung.tistory.com/279

(1) 틀린 점

(2) 배운 점