[백준 JAVA] 31932 : 나는 북극곰입니다

[백준 31932] 나는 북극곰입니다 : https://www.acmicpc.net/problem/31932

---

문제 조건 정리

 

1. N개의 빙하(정점)와 M개의 얼음 다리(간선)로 이뤄진 북극(그래프)이 있다.
2. 간선은 양방향(무향)이다.
3. 간선은 시간에 따라 녹아서 무너진다.
4. 북극곰은 1번 빙하에서만 사냥할 수 있다. 최대한 오래 머물고 싶다.
5. 북극곰은 N번 빙하로 도착해야만 한다. 사냥을 최대한 오래하되 N번 빙하로 도착은 해야 한다.
6. 북극곰은 1초마다 움직이거나, 사냥할 수 있다. 둘 중 하나만 할 수 있다.
7. 북극곰은 무너진 다리와 건너는 와중에 무너질 다리를 건널 수 없다.
   다리를 건너는 것을 완료하는 시점과 다리가 무너지는 시점이 동일하다면 건널 수 있는 것으로 간주한다.
   즉, k초가 지났고, 얼음 다리 길이가 d, 얼음 다리가 t초에 무너진다면 k+d<=k를 만족해야 함.
   
   
8. 북극곰이 1번 빙하에서 최대한 오래 사냥할 수 있는 시간을 구하자.
   == 북극곰이 1번 빙하에서 몇 초간 움직이지 않을 수 있는가?
   == 북극곰이 1번 빙하에서 몇 초부터 움직이면 되는가?

---

입력 / 출력

---

문제를 풀기 전

 

1. 북극곰이 1번 빙하에서 최대한 오래 사냥할 수 있는 시간을 구하자.
   == 북극곰이 1번 빙하에서 몇 초간 움직이지 않을 수 있는가?
   == 북극곰이 1번 빙하에서 몇 초부터 움직이면 되는가?
   
   
2. 움직인다는 것은 최대한 빠르게 도착점으로 이동하는 것, 가중치가 존재, 음수가 없는 가중치 -> 다익스트라
   
   다익스트라 시간 복잡도
   -> 간선(Edge), 정점(Vertex)
   -> 우선순위 큐에서 최소 원소를 추출하는 작업이 log V의 시간 복잡도를 가지며, 이 작업이 간선의 수 E만큼 반복
   
   
3. 0초 출발, 1초 출발, 2초 출발, ... , 건너는 도중 다리 무너지지 않게 딱 맞춰서 출발(N초 출발) -> 완전탐색
   출발할 시간을 차례대로 검색 -> O(N) * 다익스트라(O(E logV)
4. 출발할 시간을 이분 탐색으로 검색 -> O(logN) * 다익스트라(O(E logV)
   이분 탐색으로 출발 시간을 짐작하고, N번 정점까지 도달할 수 있다면 출발 시간을 늦추는 방법으로 진행하면 되겠다!
   
   
5. 이걸 반대로 생각해 보자면?
   도착점에서 출발점으로 이동하면서 각 정점에 "늦어도 이때까지는 와야 한다"와 같은 데드라인을 정해주는 것은 어떨까?
   그리고 그 데드라인을 최대화하며 출발점에 닿는 순간, 즉 출발점에 데드라인이 정해지는 순간 탐색 종료
   (다익스트라의 그리디함을 이용 *우선순위큐) -> 다익스트라(O(E logV))

---

이분탐색을 활용한 정방향 탐색 코드

 

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ31932 {

    private static class Edge {
        int to, dist, breakTime;

        public Edge(int to, int dist, int breakTime) {
            this.to = to;
            this.dist = dist;
            this.breakTime = breakTime;
        }

    }

    private static class Bear implements Comparable<Bear> {
        int pos, time;

        public Bear(int pos, int time) {
            this.pos = pos;
            this.time = time;
        }

        @Override
        public int compareTo(Bear o) {
            return this.time - o.time;
        }
    }


    static int n, m;
    static List<List<Edge>> graph;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");

        n = Integer.parseInt(stringTokenizer.nextToken());
        m = Integer.parseInt(stringTokenizer.nextToken());

        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 1; i <= m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            int u = Integer.parseInt(stringTokenizer.nextToken());
            int v = Integer.parseInt(stringTokenizer.nextToken());
            int d = Integer.parseInt(stringTokenizer.nextToken());
            int t = Integer.parseInt(stringTokenizer.nextToken());

            graph.get(u).add(new Edge(v, d, t));
            graph.get(v).add(new Edge(u, d, t));
        }


        int start = 0; // 최소 물고기
        int end = 0;// 최대 물고기

        // 1번 노드와 인접한 간선 모두를 탐색하며 가장 늦게 출발할 수 있는 시간 검색
        for (Edge edge : graph.get(1)) {
            end = Math.max(end, edge.breakTime - edge.dist); // 최대 물고기
        }


        // 1번 노드에서 사냥할 수 있는 최대 시간이 0초라면?
        // 도착 가능 여부 검사
        if (end == 0) {
            if (dijkstra(0)) {
                System.out.println(0);
            } else {
                System.out.println(-1);

            }
            return;
        }

        // 이분탐색
        while (start <= end) {
            int mid = (start + end) / 2;

            // 조건을 만족한다면?
            // 더 큰 값을 탐색하도록.
            if (dijkstra(mid)) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        System.out.println(end);

    }

    private static boolean dijkstra(int huntTime) {
        PriorityQueue<Bear> pq = new PriorityQueue<>();
        int[] bestRecord = new int[n + 1];  // 각 노드에 도달할 때의 최적 시간을 저장하는 배열
        Arrays.fill(bestRecord, Integer.MAX_VALUE);  // 초기값

        pq.offer(new Bear(1, huntTime));
        bestRecord[1] = huntTime;  // 출발 지점 초기 시간을 설정

        while (!pq.isEmpty()) {
            Bear curr = pq.poll();

            // 이미 최적의 시간으로 방문한 노드라면 스킵
            if (curr.time > bestRecord[curr.pos]) continue;

            // 목적지에 도달
            if (curr.pos == n) {
                return true;
            }

            for (Edge nextEdge : graph.get(curr.pos)) {
                int newTime = curr.time + nextEdge.dist;

                // 다리가 무너지기 전에 도착할 수 없는 경우 스킵
                if (nextEdge.breakTime < newTime) continue;

                // 더 최적의 시간으로 도달할 수 있는 경우에만 업데이트하고 큐에 넣음
                if (newTime < bestRecord[nextEdge.to]) {
                    bestRecord[nextEdge.to] = newTime;
                    pq.offer(new Bear(nextEdge.to, newTime));
                }
            }
        }
        
        // 목적지 도달 실패
        return false;
    }

}

 

 

 

역방향 탐색 코드

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ31932 {

    // 간선
    // 도착지, 거리, 그리고 다리가 무너지는 시간
    private static class Edge {
        int to;
        int dist, breakTime;

        public Edge(int to, int dist, int breakTime) {
            this.to = to;
            this.dist = dist;
            this.breakTime = breakTime;
        }
    }

    // 노드
    // 현재 위치, 도달 가능한 데드라인(deadline)
    private static class Node implements Comparable<Node> {
        int idx;
        int deadLine;

        public Node(int idx, int deadLine) {
            this.idx = idx;
            this.deadLine = deadLine;
        }

        @Override
        public int compareTo(Node other) {
            // 데드라인이 큰 노드를 우선 처리하기 위해 내림차순으로 정렬
            return other.deadLine - this.deadLine;
        }
    }

    static int n, m;
    static List<List<Edge>> graph;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");

        n = Integer.parseInt(stringTokenizer.nextToken()); // 노드의 수
        m = Integer.parseInt(stringTokenizer.nextToken()); // 간선의 수

        // 그래프 초기화
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 정보 입력
        for (int i = 1; i <= m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            int u = Integer.parseInt(stringTokenizer.nextToken());
            int v = Integer.parseInt(stringTokenizer.nextToken());
            int d = Integer.parseInt(stringTokenizer.nextToken());
            int t = Integer.parseInt(stringTokenizer.nextToken());

            if (d > t) continue; // 거리가 다리가 무너지기 전까지 도달할 수 없는 경우

            // 무방향 그래프이므로 양방향으로 간선 추가
            graph.get(u).add(new Edge(v, d, t));
            graph.get(v).add(new Edge(u, d, t));
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] bestDeadLine = new int[n + 1]; // 각 노드에 대해 도달 가능한 최적의 데드라인 (클수록 좋음)
        Arrays.fill(bestDeadLine, -1); // 모든 노드의 데드라인을 무효한 값으로 초기화

        // 도착 지점(n번 노드, 사실상 출발 지점)의 인접 노드에 대해 초기화
        for (Edge edge : graph.get(n)) {
            pq.offer(new Node(edge.to, edge.breakTime - edge.dist));
            bestDeadLine[n] = Math.max(bestDeadLine[n], edge.breakTime); // 도착 지점에서의 데드라인 갱신
            bestDeadLine[edge.to] = edge.breakTime - edge.dist; // 인접 노드의 초기 데드라인 설정
        }

        // 다익스트라 알고리즘
        while (!pq.isEmpty()) {
            Node curr = pq.poll();

            // 기록된 데드라인이 더 크다면 현재 노드 무시
            if(curr.deadLine < bestDeadLine[curr.idx]) continue;
            bestDeadLine[curr.idx] = curr.deadLine;

            // 목표 지점(1번 노드)에 도달한 경우
            if (curr.idx == 1) {
                System.out.println(curr.deadLine);
                return;
            }

            // 인접한 노드들을 탐색하며 데드라인 갱신
            for (Edge adjEdge : graph.get(curr.idx)) {
                // 다음 노드의 데드라인 계산
                // 1. 현재 노드의 데드라인 - 간선의 거리
                // 2. 간선이 무너지는 시간 - 간선의 거리
                // 둘 중에서 작은 값이 유효한 다음 노드의 데드라인
                int nextNodeDeadLine = Math.min(curr.deadLine, adjEdge.breakTime) - adjEdge.dist;

                // 도달할 수 없거나 이미 더 좋은 데드라인이 있는 경우 무시
                if (nextNodeDeadLine <= bestDeadLine[adjEdge.to]) continue;

                bestDeadLine[adjEdge.to] = nextNodeDeadLine; // 데드라인 갱신
                pq.offer(new Node(adjEdge.to, nextNodeDeadLine)); // 다음 노드를 큐에 추가
            }
        }

        // 목표 지점에 도달할 수 없는 경우
        System.out.println(-1);
    }
}

---

 

문제를 풀고 난 후

 

정방향으로 탐색하는 첫 번째 코드의 이분 탐색에서 배열 내의 lower, upper bound를 찾는 것이 아니라 조건을 만족하는 올바른 값을 찾는 이분 탐색을 일반화하느라 조금 헷갈렸다. 결과적으로 이해하고 이전 글을 수정해 뒀다.

https://mak-ing.tistory.com/33

[이분탐색] Upper / Lower Bound

사실 역방향으로 탐색하는 두 번째 코드에서 엄청 고생했다. 생각보다 우선순위 큐에 대해 섬세한 처리가 필요했다. 중복되거나 불필요한 연산들이 많이 숨어있었는데 그것들을 모두 조건 처리함으로 단 한 번의 다익스트라로 문제를 해결해서 훨씬 효율적으로 풀이할 수 있었다.

 

백준 채점 현황을 너무 더럽혀둬서 미안할 수준이다. 덕분에 논리나 최적화 두 가지 모두 부족했고 많이 배웠던 문제였음.