백준 14217 - 그래프 탐색

문제

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

리뷰

BFS나 다익스트라를 이용하여 풀이할 수 있는 문제였다. 필자는 다익스트라로 풀이했다.

그래프의 간선 정보가 갱신된 후 각 도시별로 수도를 방문하는데 필요한 최소
도시 수를 구하는 문제이다. 양방향 그래프이기 때문에 그래프를 갱신하고 수도를
시작점으로 삼아 다익스트라를 돌려주면 dist 배열을 통해 결과를 바로 도출할 수
있을 것 같아 해당 아이디어를 바탕으로 로직을 구성하였다.

간선 정보를 쉽게 갱신하기 위해 인접행렬의 형태로 그래프를 정의하였다.
로직의 시간복잡도는 다익스트라 로직을 포함한 q 의 while 절에서 가장 큰
$O(qn\log n)$의 형태로 수렴하고 최악의 경우에도 $500*500log500$ 의 연산을
수행하므로 문제의 시간 제한 조건인 2초를 무난히 통과할 수 있다.

코드

import java.util.*;

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

public class Main {
    static int n, m;
    static int[][] map;
    static int[] dist;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());
        n = parseInt(st.nextToken());
        m = parseInt(st.nextToken());

        map = new int[n + 1][n + 1];
        dist = new int[n + 1];

        while (m-- > 0) {
            st = new StringTokenizer(in.nextLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());

            map[u][v] = 1;
            map[v][u] = 1;
        }

        int q = parseInt(in.nextLine());
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            st = new StringTokenizer(in.nextLine());
            int a = parseInt(st.nextToken());
            int i = parseInt(st.nextToken());
            int j = parseInt(st.nextToken());

            map[i][j] = map[j][i] = a == 1 ? 1 : 0;
            dijkstra(1);
            for (int node = 1; node < dist.length; node++) {
                int result = dist[node] == MAX_VALUE ? -1 : dist[node];
                sb.append(result + " ");
            }
            sb.append("\n");
        }

        System.out.print(sb);
        in.close();

    }

    static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.weight));
        Arrays.fill(dist, MAX_VALUE);
        dist[start] = 0;
        pq.offer(new Node(start, dist[start]));

        while (!pq.isEmpty()) {
            Node current = pq.poll();

            if (dist[current.number] < current.weight)
                continue;

            for (int i = 0; i < map[current.number].length; i++) {
                if (map[current.number][i] == 1 && dist[i] > dist[current.number] + 1) {
                    dist[i] = dist[current.number] + 1;
                    pq.offer(new Node(i, dist[i]));
                }
            }
        }

    }

    static class Node {
        int number, weight;

        public Node(int number, int weight) {
            this.number = number;
            this.weight = weight;
        }
    }
}

결과