백준 5214 - 환승

문제

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

리뷰

BFS나 다익스트라 알고리즘을 활용하여 풀이할 수 있는 문제였다.

처음에 단순히 하이퍼링크 노드 정보만 모아두는 Map을 따로 선언하고
BFS 로직내에서 노드마다 속한 하이퍼링크를 통해 방문할 수 있는 모든 노드를
큐에 넣는 식으로 구현하였더니 시간 초과가 발생했다. 이에 따라 새로운 방식으로
접근하였다.

하이퍼링크를 정점으로 간주하고 해당 링크에 포함된 정점들과 하이퍼링크 정점간
간선을 설정해준다. 그래프를 이렇게 설정하면 하이퍼링크을 통하여 이동할 경우의
비용 처리만 적절히 처리해주면 앞서 언급했던 두 알고리즘을 적절히 활용하여
로직을 구성할 수 있다. 각각의 로직에서 사용되는 visited , dist 배열의
크기를 N+M+1 로 정의한 후 N+1~N+M 의 범위 하이퍼링크 정점을
나타내는데 사용하였다.

BFS
주어진 하이퍼링크 정점이 포함된 그래프에서 하이퍼링크로 넘어갈때만 노드 수를
증가시키지 않고, 목표로 하는 정점에 도달했을 시 해당 정점까지의 비용을 반환하는
식으로 로직을 구성하였다.

간선의 개수가 $KM$ 개이고 정점의 개수가 $N+M$ 개라 bfs 로직의 시간복잡도는
단순 계산시 $O(KM(N+M))$ 으로 수렴하나, 실질적인 연산 횟수는 그보다 훨씬
낮기에 주어진 제한 조건을 무난히 통과할 수 있다.

다익스트라
주어진 하이퍼링크 정점이 포함된 그래프에서 dist 를 이용하여 다익스트라를
수행하면 dist[N] 에는 하이퍼링크 정점을 포함한 노드 수가 저장된다.
(하이퍼링크 정점 + 하이퍼링크내 속한 정점)
따라서 의도한 답을 도출하기 위해 dist[N]/2+1 연산을 해주었다.

로직의 시간복잡도는 $O(ElogV) \rightarrow O(KM \log (N+M))$ 으로
수렴하므로 주어진 제한 조건을 무난하게 통과할 수 있다.

코드

BFS 이용

import java.util.*;

import static java.lang.Integer.*;

public class Main {
    static boolean[] visited;
    static List<List<Integer>> graph = new ArrayList<>();
    static int N, K, M;

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

        N = parseInt(st.nextToken());
        K = parseInt(st.nextToken());
        M = parseInt(st.nextToken());

        visited = new boolean[N + M + 1];

        for (int i = 0; i <= N + M; i++)
            graph.add(new ArrayList<>());

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(in.nextLine());
            while (st.hasMoreTokens()) {
                int node = parseInt(st.nextToken());
                graph.get(node).add(N + i);
                graph.get(N + i).add(node);
            }
        }

        int result = bfs(1, N);
        System.out.println(result);
        in.close();
    }

    static int bfs(int start, int end) { // O((KM)(N+M))
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(start, 1));
        visited[start] = true;

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if (current.num == end)
                return current.level;

            for (Integer next : graph.get(current.num)) { // O(K)
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(new Node(next, next > N ? current.level : current.level + 1));
                }
            }
        }

        return -1;
    }


    static class Node {
        int num, level;

        public Node(int num, int level) {
            this.num = num;
            this.level = level;
        }
    }
}

다익스트라 이용

import java.util.*;

import static java.lang.Integer.*;

public class Main {
    static int[] dist;
    static List<List<Integer>> graph = new ArrayList<>();

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

        int N = parseInt(st.nextToken());
        int K = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

        dist = new int[N + M + 1];

        for (int i = 0; i <= N + M; i++)
            graph.add(new ArrayList<>());

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(in.nextLine());
            while (st.hasMoreTokens()) {
                int node = parseInt(st.nextToken());
                graph.get(node).add(N + i);
                graph.get(N + i).add(node);
            }
        }

        dijkstra(1);
        System.out.print(dist[N] == MAX_VALUE ? -1 : dist[N] / 2 + 1);
        in.close();
    }

    static void dijkstra(int start) { // O( KM log (N+M) )
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.level));
        Arrays.fill(dist, MAX_VALUE);
        dist[start] = 1;
        pq.offer(new Node(start, dist[start]));

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

            if (dist[current.num] < current.level)
                continue;

            for (Integer next : graph.get(current.num)) {
                if (dist[next] > dist[current.num] + 1) {
                    dist[next] = dist[current.num] + 1;
                    pq.offer(new Node(next, current.level + 1));
                }
            }
        }

    }
    

    static class Node {
        int num, level;

        public Node(int num, int level) {
            this.num = num;
            this.level = level;
        }
    }
}

결과

BFS를 이용한 경우가 다익스트라보다 좀 더 빠른 수행 시간을 보인다.
아무래도 다익스트라는 N+M 전 범위에 대해 최단 경로 비용을 도출하고
BFS는 목표로 하는 지점에 도달할 경우 탐색을 중단하기 때문에 그런듯 싶다.