[자바] 백준 2842 - 집배원 한상덕 (java)

 문제 : boj2842

---

 

필요 알고리즘 개념

• 투 포인터, 그래프 탐색
  
  • 당연히 bfs나 dfs 문제처럼 생겼는데, dfs나 bfs는 그저 탐색을 위해 거들뿐인 문제이다. 투 포인터 혹은 이분탐색 등을 사용해 범위를 조정해나가는 아이디어가 필요하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  혹시 BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고하자. 투 포인터는 써둔게 없지만 유명하기도 하고 플래 문제 풀려고 하는 정도라면 당연히 알거라 생각된다.

 

  우선 N이 50으로 매우 작다. 3초이므로 O(N^5) 정도까지도 비벼볼 수 있는 혜자 문제이긴 하다. 그렇다고 그냥 브루트포스로 갈 수 있는 모든 길을 살펴보기엔 O(2^N) 수준으로 나올테니 불가능하다.

 

  약간만 생각을 바꾸면 방법을 찾을 수 있는데, N이 매우 작다는걸 이용해야 한다. 고도는 1,000,000 까지긴 하지만, 애초에 존재 가능한 마을은 N^2으로 2500개이다. 그렇다면 서로 다른 고도의 수는 2500개를 초과할 수 없다. 그럼 모든 고도 구간 [s, e] (s<=e, 고도 s부터 e 이하)에 대해 bfs혹은 dfs가 가능한지 살펴보면 어떨까? 대략 O(N^6)정도가 필요할테니 안될것이다. 하지만 시간을 좀 줄일 수 있다면 될것도 같이 생겼다. 그럼 투포인터 혹은 이분탐색으로 범위를 조정해보면 어떨까? 그럼 가능하다! 결론적으로 대략 O(N^3)정도로 풀 수 있다. 이하 투 포인터를 이용한 풀이방식이고, 좀 더 최적화 하기 위한 부분도 있다.

 

1. P 또는 K 위치의 고도들에 대해 최소값과 최대값을 따로 구해둔다. -> 어차피 모든 P, K를 모두 지나쳐야 하므로 이 최소, 최대값을 포함하는 구간을 포함하는 구간만 보면 된다.

 

2. 존재했던 고도들을 정렬한다. 투 포인터에 사용할꺼다.

 

3. [s, e] 구간을 보기 위해 투 포인터 규칙을 설정하자. 내 경우엔 s는 고도 중 최소값, e는 '1'에서 찾은 최대값으로 설정했다. 이 경우, 설정한 [s, e]로 P에서 출발해 모든 K를 탐색하는게 가능하다면 s++를 통해 구간을 줄이고, 찾지 못했다면 e++를 통해 구간을 늘리면 된다. s, e 값을 조정해나가며 가장 작은 구간을 찾아주면 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;

interface Type {
    public static final char POST_OFFICE = 'P';
    public static final char HOUSE = 'K';
    public static final char GROUND = '.';
}

class Pos {
    int r, c, altitude;
    char type;
    public Pos(int r, int c, char type) {
        this.r = r;
        this.c = c;
        this.type = type;
    }
    public boolean isPostOffice() {
        return type == Type.POST_OFFICE;
    }
    public boolean isHouse() {
        return type == Type.HOUSE;
    }
    public boolean isNotGround() {
        return type != Type.GROUND;
    }
}

public class Main {
    Pos start;
    Pos[][] arr;
    int n, min, max, houseCount = 0;
    TreeSet<Integer> ts;
    private static final int[] DR = {1, 0, 0, -1, -1, -1, 1, 1};
    private static final int[] DC = {0, 1, -1, 0, -1, 1, -1, 1};

    private boolean isPossible(int low, int high) {
        boolean[][] v = new boolean[n][n];
        int remain = houseCount;
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{start.r, start.c});
        v[start.r][start.c] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int d = 0; d < 8; d++) {
                int nr = cur[0]+DR[d];
                int nc = cur[1]+DC[d];
                if (nr<0||nr>=n||nc<0||nc>=n||v[nr][nc]) continue;
                int nextAltitude = arr[nr][nc].altitude;
                if (nextAltitude<low || nextAltitude>high) continue;
                if (arr[nr][nc].isHouse())
                    remain--;
                if (remain == 0)
                    return true;
                v[nr][nc] = true;
                q.add(new int[]{nr, nc});
            }
        }
        return false;
    }

    private int getAnswer() {
        int low = ts.pollFirst();
        int high = max;
        int answer = 1000001;

        while (low <= min) {
            if (isPossible(low, high)) {
                answer = Math.min(answer, high - low);
                if (ts.isEmpty())
                    break;
                low = ts.pollFirst();
            } else {
                if (ts.isEmpty())
                    break;
                if (ts.higher(high) == null)
                    break;
                high = ts.higher(high);
            }
        }

        return answer;
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new Pos[n][n];
        min = 1000001;
        max = 0;
        start = null;
        for (int r = 0; r < n; r++) {
            String row = br.readLine();
            for (int c = 0; c < n; c++) {
                arr[r][c] = new Pos(r, c, row.charAt(c));
                if (arr[r][c].isPostOffice())
                    start = arr[r][c];
                if (arr[r][c].isHouse())
                    houseCount++;
            }
        }
        ts = new TreeSet<>();
        for (int r = 0; r < n; r++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int c = 0; c < n; c++) {
                arr[r][c].altitude = Integer.parseInt(st.nextToken());
                ts.add(arr[r][c].altitude);
                if (arr[r][c].isNotGround()) {
                    min = Math.min(min, arr[r][c].altitude);
                    max = Math.max(max, arr[r][c].altitude);
                }
            }
        }
        System.out.println(getAnswer());
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}