[BJ] 2842 집배원 한상덕

BJ P5 2842 집배원 한상덕

 

 

문제링크

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

2842번: 집배원 한상덕

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/oNqMTOIyLrI

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.platinum.l5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeSet;

/**
 * @author 은서파
 * @since 2022. 12. 22.
 * @see https://www.acmicpc.net/problem/2842
 * @git
 * @youtube
 * @performance 22164 488
 * @category #투포인터, #그래프이론
 * @note
 */

public class BJ_P5_02842_집배원한상덕 {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;

    static int N;
    static Point[][] map;
    static Point POST;
    static int HOME_CNT;
    static int MIN_TIRE_RATE = Integer.MAX_VALUE;

    static int[][] deltas = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(input.readLine());
        map = new Point[N][N];
        for (int r = 0; r < N; r++) {
            String line = input.readLine();
            for (int c = 0; c < N; c++) {
                map[r][c] = new Point(r, c, line.charAt(c));
                if (map[r][c].t == 'P') {
                    POST = map[r][c];
                } else if (map[r][c].t == 'K') {
                    HOME_CNT++;
                }
            }
        }
        // 고도 처리
        TreeSet<Integer> hset = new TreeSet<>(); // 중복 방지, 크기순 정렬
        for (int r = 0; r < N; r++) {
            tokens = new StringTokenizer(input.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c].h = Integer.parseInt(tokens.nextToken());
                hset.add(map[r][c].h);
            }
        }
        List<Integer> hlist = new ArrayList<>(hset);
        // 탐색할 범위 골라보기
        for (int si = 0, ei = 0; si <= ei && ei < hlist.size();) {
            //si~ ei의 범위에서 탐색 시작!!
            int sh = hlist.get(si);
            int eh = hlist.get(ei);
            // 출발점 - 우체국!!(우체국이 범위에 포함되어야 한다.)
            if (POST.h >= sh && POST.h <= eh) {
                // 완탐!!
                boolean[][] visited = new boolean[N][N];
                int finded = dfs(POST, visited, sh, eh);
                // 다 찾았다면 --> 좀 더 범위를 줄여가보자. - > si++
                if (finded == HOME_CNT) {
                    MIN_TIRE_RATE = Math.min(MIN_TIRE_RATE, eh - sh);
                    si++;
                }
                // 못찾았다면 범위를 늘여가보자.
                else {
                    ei++;
                }
            }
            // 범위에 들어가지 않는다면 범위를 넓혀보자.
            else {
                ei++;
            }
        }

        System.out.println(MIN_TIRE_RATE);
    }

    private static int dfs(Point point, boolean[][] visited, int sh, int eh) {
        visited[point.r][point.c] = true;

        int cnt = 0;
        for (int d = 0; d < deltas.length; d++) {
            int nr = point.r + deltas[d][0];
            int nc = point.c + deltas[d][1];

            // 범위 내에 있고 미방문이고 sh ~ eh 사이에 있다면 방문!!
            if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc].h >= sh && map[nr][nc].h <= eh) {
                if (map[nr][nc].t == 'K') {
                    cnt++;
                }
                cnt += dfs(map[nr][nc], visited, sh, eh);
            }
        }
        return cnt;
    }

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

    static class Point {
        int r, c, h;
        char t;

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

    // REMOVE_START
    public static String instr = "3\n"
                                 + "K.P\n"
                                 + "...\n"
                                 + "K.K\n"
                                 + "3 3 4\n"
                                 + "9 5 9\n"
                                 + "8 3 7";
    // REMOVE_END

}