백준 2842번 - 집배원 한상덕

황제연·2025년 1월 26일

2842번 BFS 백준 자바 집배원 한상덕 투포인터

알고리즘

목록 보기

166/169

문제 탐색하기

입력 자료 정리

n은 마을을 나타내는 행렬과 피로도를 나타내는 행렬의 가로/세로크기다
이어서 들어오는 행렬은 마을을 나타내는 char형 입력값이다
P는 시작위치고 하나만 존재한다. .은 목초지인데 그냥 빈칸이다
k는 집이며, 방문해야할 장소다
이어서 들어오는 값들은 각 위치의 고도다

해결방법 추론

일단 모든 집배원 위치에서 모든 집을 방문하는 것은 BFS로 해결할 수 있을 것이다
그런데 어떤 고도 범위에서 탐색을 할지 정하는 것은 시간초과가 발생할 수 있다
따라서 고도의 최소와 최대 범위를 구하기 위해서는 시간복잡도를 줄일 방법을 생각해야한다
이번에는 투포인터로 해결했다. 최소와 최대 범위라는 두개만 생각하면 되기 떄문이다
투포인터를 위해 모든 고도를 구한다음 리스트에 넣어준다. 그리고 최대와 최소고도도 구한다
투포인터의 대상은 반드시 처음이 되는 0번 인덱스 지점과 최대 높이의 인덱스 위치를 나타내도록 잡는다
그리고 left에 있는 포인터는 최소고도의 인덱스 범위를 벗어나지 말아야하며, right에 있는 포인터는 최대 범위인 리스트의 크기를 벗어나지 말아야한다
이때 투포인터의 각 값들을 꺼낸다음 bfs를 돌려준다
bfs는 최대한 모든 집을 방문할 때까지 탐색하는데, 만약 투포인터 범위내의 고도가 아닌 경우 탐색하지 않는다
만약 현재 투포인터 범위에서 모든 집을 방문할 수 있다면 정답 변수와 최솟값을 비교해준다
피로도의 최솟값을 구해야하니까 투포인터의 차이와 비교하면 될 것이다
그리고 만약 모든 집을 방문할 수 있으면 최소 범위의 포인터를 변화시키고 반대는 최대범위의 포인터를 변화시킨다
이렇게 투포인터와 BFS를 섞는다면 문제를 해결할 수 있을 것이다

시간복잡도 계산

시간복잡도는 투포인터에서 N^2의 연산이 발생하고 bfs에서 n^2의 연산이 발생한다
따라 시간복잡도는 O(n^2)이며, 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

n은 int형 변수로 관리하고 시작 위치도 크기가 2인 배열로 관리한다
먼저 마을을 나타내는 행렬은 char형 2차원 배열로 관리하고 고도는 int형 2차원 배열로 관리한다
고도의 정렬을 위한 리스트를 하나 선언한다. 그리고 최대와 최소를 구할 변수도 하나씩 선언한 뒤 고도를 입력받을 때 모두 갱신해준다
left는 0, right는 최대 고도의 처음 인덱스, 그리고 범위 내에서 이루어지도록 최소 높이의 리스트 인덱스와 최대 범위의 리스트 값을 각각 초기화해준다
ans는 정답으로 출력할 값인데 최소값을 구하기 위해 Integer.MAX_VALUE로 초기화한다

투포인터 설계

left는 minHiehgt보다 작거나 같아야하고, right는 maxHeight보다 작아야한다.
또한 두 조건을 만족시키면서 left <= right 조건도 만족시키는 선에서 투포인터 탐색을 진행한다
left 위치의 리스트 값과 right 위치의 리스트 값을 하나씩 뽑아준다. 해당 고도범위는 앞으로의 bfs 탐색에서 조건으로 활용할 것이다
BFS 탐색 결과 모든 집을 방문할 수 있다는 0을 리턴하면 정답을 최솟값으로 갱신한다
이때 ans와 비교할 값은 피로도다
참고로 피로도는 가장 높은 고도 - 가장 낮은 고도이므로 left - right가 성립된다
만약 모든 집을 방문할 수 있다면 더 가능한 최소범위내에서 찾기 위해 left를 증가시키고 반대는 right를 증가시킨다

bfs설계

bfs는 다른 8방 BFS와 동일하게 구현한다
다만 두가지만 다르게 생각하면 된다. 먼저 종료조건으로 h가 0이면 0을 리턴한다
h는 남은 방문집의 수를 의미한다
이어서 앞서 파라미터로 받은 최소/최대 고도의 범위내에 포함되는 것만 큐에 넣어준다
만약 해당 위치의 값이 K라면 h값을 감소시킨다.
bfs 탐색이 종료되면 h를 리턴한다

출력값 설계

완성한 ans를 출력하면 된다.

정답 코드

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

public class Main {

    static int n;
    static char[][] arr;
    static int[][] fatigue;
    static int[] dy = {-1,-1,-1,0,0,1, 1,1};
    static int[] dx = {-1,0,1,-1,1,-1,0,1};
    static int[] start;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        arr = new char[n][n];
        start = new int[2];
        fatigue = new int[n][n];
        int home = 0;
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < n; j++) {
                arr[i][j] = s.charAt(j);
                if(arr[i][j] == 'P'){
                    start[0] = i;
                    start[1] = j;
                }
                if(arr[i][j] == 'K'){
                    home++;
                }
            }
        }
        int max = -1;
        int min = Integer.MAX_VALUE;
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                fatigue[i][j] = Integer.parseInt(st.nextToken());
                list.add(fatigue[i][j]);
                if(arr[i][j] == 'P' || arr[i][j] == 'K'){
                    max = Math.max(max, fatigue[i][j]);
                    min = Math.min(min, fatigue[i][j]);
                }
            }
        }
        Collections.sort(list);
        int left = 0;
        int right = list.indexOf(max);
        int minHeight = list.indexOf(min);
        int maxHeight = list.size();
        int ans = Integer.MAX_VALUE;
        while(left <= minHeight && left <= right && right < maxHeight){
            int a = list.get(left);
            int b = list.get(right);
            if(bfs(a,b, home) == 0){
                ans = Math.min(ans, b-a);
                left++;
            }else{
                right++;
            }
        }

        bw.write(ans+"");

        br.close();
        bw.close();
    }

    private static int bfs(int min, int max, int h) {
        boolean[][] visited = new boolean[n][n];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start[0], start[1]});
        visited[start[0]][start[1]] = true;
        while(!q.isEmpty()){
            int[] now = q.poll();
            if(h == 0){
                return 0;
            }

            for (int i = 0; i < 8; i++) {
                int ny = now[0] + dy[i];
                int nx = now[1] + dx[i];
                if(isRange(ny,nx) && !visited[ny][nx] &&fatigue[ny][nx] >= min && fatigue[ny][nx] <= max){
                    visited[ny][nx] = true;
                    if(arr[ny][nx] == 'K'){
                        h--;
                    }
                    q.add(new int[]{ny,nx});
                }
            }
        }
        return h;
    }

    private static boolean isRange(int ny, int nx) {
        return ny >= 0 && ny < n && nx >=0 && nx < n;
    }
}