백준 이상적인 경로(3526)

이상적인 경로

1. 힌트

1) 사전순으로 가장 앞선 경로를 찾으려면 $1$번 방에서 시작해서 언제나 가장 사전순으로 작은 간선만을 이용하면 됩니다.

2) 동시에 최단경로여야 하므로 최단 경로에 속하는 정점으로만 이동해야 합니다 $N$번 정점에서 거꾸로 BFS를 해서 dist배열을 완성한 뒤 dist[here] - 1 = dist[there]인 경우 there은 최단 경로가 지나는 정점임을 알 수 있습니다.

3) BFS를 통해 이상적인 경로를 역추적하는 과정에서 간선을 확인하면서 가장 작은 가중치의 간선을 모두 Queue에 넣습니다. 이러한 간선은 여러개가 있을 수 있습니다.

2. 접근

1) 최단 경로

$(1, N)$의 최단 경로의 길이는 간선의 가중치를 무시하고 단순하게 BFS를 통해서 구할 수 있습니다. 그런데 최단 경로이면서 동시에 사전순으로 가장 앞서는 경로는 어떻게 찾을 수 있을까요? 만약 최단 경로임을 고려하지 않는다면 언제나 사전순으로 가장 앞서는 간선만 이용하면 사전 순으로 가장 앞선 경로를 찾을 수는 있습니다. 그런데 이건 최단 경로는 아니죠.

2) 역추적

6 5
1 2 7
2 4 8
1 3 8
3 5 9
5 6 10
=>
3
8 9 10

빨간색은 $1$번 정점에서 시작한 BFS의 dist배열을 나타내고 파란색은 간선의 가중치를 의미합니다. 이상적인 경로를 찾기 위해서는 최단 경로에 속하면서 사전순으로 가장 앞선 경로로만 이동해야합니다. 최단 경로가 지나는 정점인지 쉽게 알 수 있는 방법이 있습니다.

바로 $N$번 정점에서 BFS를 시작해서 dist배열을 만드는 것입니다. dist[here] - 1 = dist[there]이라면 there정점으로 이동하면 언제나 최단경로임을 보장할 수 있죠. 단, 이러한 최단 경로가 여러 개 있는 경우는 모두 이동해봐야합니다. 따라서 사전 순으로 가장 앞서는 길이가 $1$인 경로, $2$인 경로 ... 순으로 BFS를 이용해서 역추적합니다.

3. 구현

public class Main {
    static int N;
    static ArrayList<ArrayList<Pair>> adj;
    static int[] dist;

    static void bfs(StringBuilder bw) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(N);
        dist = new int[N + 1];
        Arrays.fill(dist, -1);
        dist[N] = 0;
        while (!q.isEmpty()) {
            int here = q.poll();
            for (Pair p : adj.get(here)) if (dist[p.index] == -1) {
                int there = p.index;
                q.offer(there);
                dist[there] = dist[here] + 1;
            }
        }
        bw.append(dist[1]).append("\n");
    }

    static void construct(StringBuilder bw) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        boolean[] booked = new boolean[N + 1];
        booked[1] = true;
        while (!q.isEmpty()) {
            int size = q.size();
            // 사전순으로 가장 작은 가중치를 구한다
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < size; i++) {
                int here = q.poll();
                for (Pair p : adj.get(here)) {
                    int there = p.index;
                    if (dist[here] - 1 == dist[there]) {
                        min = Math.min(min, p.value);
                    }
                }
                q.offer(here);
            }
            if (min != Integer.MAX_VALUE) bw.append(min).append(" ");
            // 사전순으로 가장 작은 가중치를 갖는 간선이 여러개라면 모두 방문
            for (int i = 0; i < size; i++) {
                int here = q.poll();
                for (Pair p : adj.get(here)) {
                    int there = p.index;
                    if (p.value == min && !booked[there] &&
                    dist[here] - 1 == dist[there]) {
                        q.offer(there);
                        booked[there] = true;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder bw = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        adj = new ArrayList<>();
        for (int i = 0; i <= N; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            adj.get(a).add(new Pair(b, c));
            adj.get(b).add(new Pair(a, c));
        }
        for (int i = 0; i <= N; i++) Collections.sort(adj.get(i));
        bfs(bw);
        construct(bw);
        System.out.println(bw);
    }

}
class Pair implements Comparable<Pair> {
    int index, value;

    Pair(int i, int v) { index = i; value = v; }

    @Override
    public int compareTo(Pair o) { return value - o.value; }
}

1) 시간 복잡도

모든 정점은 Queue에 단 한번만 들어가므로 BFS와 동일하게 $O(V + E)$입니다.

2) 테스트 케이스

6 5
1 2 7
2 4 8
1 3 8
3 5 9
5 6 10
=>
3
8 9 10