[BOJ 26157] 즉흥 여행 (Hard) (Java)

BOJ 26157 즉흥 여행 (Hard)

난이도 : 플래 3

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

26157번: 즉흥 여행 (Hard)

 

전략

SCC에 속한 임의의 두 정점은 방문할 수 있다.

위의 예시에서는 그래프 전체가 하나의 SCC이므로 모든 정점이 결과가 된다.

 

위의 예시에서는 SCC는 [1], [2, 3, 4] 두 개이며 SCC로 그래프를 압축하면 [1] -> [2, 3, 4] 이다.

따라서 [1]의 정점들이 결과가 된다.

 

즉, 압축한 그래프에서 모든 SCC를 방문할 수 있는 첫번째 SCC를 찾아야하므로 위상정렬을 사용할 수 있다.

 

아래의 예시에서는 결과가 없다.

 

위 예시에서는 [1, 2], [3, 4]가 SCC가 되며 압축된 그래프에서 두 SCC 사이에 간선이 없으므로 결과는 없다.

 

위상정렬 시 진입차수가 0인 SCC가 [1], [5] 두 개이므로 하나의 SCC를 선택하면 나머지를 방문할 수 없다.

만약 [5]를 선택하였다면 [2, 3, 4]를 방문한 후 [1]을 방문하여야 모든 정점을 탐색할 수 있는데,

[1] -> [2, 3, 4] 이고 [2, 3, 4] -> [1] 이면 SCC에 위배된다. 즉 [1, 2, 3, 4]여야 하기 때문이다.

 

따라서 SCC로 압축한 그래프에서 위상정렬하면서 큐의 크기가 2 이상인 경우에는 결과가 없으며,

그렇지 않은 경우 진입차수가 0인 첫번째 SCC의 정점들을 출력하도록 하면 된다.

 

위상정렬 시 큐가 빈 경우는 생기지 않는다. SCC 압축 그래프에서 DAG가 보장되기 때문이다.

 

코드

package BOJ_26157;

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

public class Main {

    static List<Integer>[] adj;
    static int[] sccId, discovered;
    static Stack<Integer> stack;
    static int sccCounter, vertexCounter;
    static List<SCC> sccList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n, m;
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);

        adj = new ArrayList[n + 1];
        discovered = new int[n + 1];
        sccId = new int[n + 1];
        sccList = new ArrayList<>();

        for (int i = 1; i < n + 1; i++) {
            adj[i] = new ArrayList<>();
            discovered[i] = -1;
            sccId[i] = -1;
        }

        for (int i = 0; i < m; i++) {
            inputs = br.readLine().split(" ");
            int from = Integer.parseInt(inputs[0]);
            int to = Integer.parseInt(inputs[1]);
            adj[from].add(to);
        }

        stack = new Stack<>();

        for (int i = 1; i < n + 1; i++) {
            if (discovered[i] == -1) {
                scc(i);
            }
        }

        compressDAG();
        SCC first = topologySort();
        if (first == null) {
            System.out.println(0);
            return;
        }

        Collections.sort(first.vertexes);
        StringBuilder sb = new StringBuilder();
        sb.append(first.vertexes.size() + "\n");
        for (int vertex : first.vertexes) {
            sb.append(vertex + " ");
        }
        System.out.println(sb);

    }

    // 그래프를 SCC 단위로 압축
    static void compressDAG() {

        for (SCC scc : sccList) {
            for (int vertex : scc.vertexes) {
                for (int next : adj[vertex]) {
                    if (scc.id != sccId[next]) {
                        SCC linkScc = sccList.get(sccId[next]);
                        scc.link.add(linkScc);
                        linkScc.inDegree++;
                    }
                }
            }
        }
    }

    // SCC 들을 위상절렬 한 후 첫번쨰 SCC 를 반환
    // 큐에 동시에 두 개 이상의 SCC 가 존재하거나 위상정렬이 불가하면 NULL 반환
    static SCC topologySort() {
        Queue<SCC> queue = new LinkedList<>();
        List<SCC> result = new ArrayList<>();

        for (SCC scc : sccList) {
            if (scc.inDegree == 0) {
                queue.offer(scc);
            }
        }

        for (int i = 0; i < sccList.size(); i++) {
            if (queue.isEmpty())
                return null;
            if (queue.size() > 1)
                return null;

            SCC cur = queue.poll();
            for (SCC next : cur.link) {
                if (--next.inDegree == 0) {
                    queue.offer(next);
                }
            }
            result.add(cur);
        }

        return result.get(0);
    }


    static int scc(int here) {
        int ret = discovered[here] = vertexCounter++;
        stack.push(here);

        for (int there : adj[here]) {
            if (discovered[there] == -1) {
                ret = Math.min(ret, scc(there));
            }
            else if (sccId[there] == -1) {
                ret = Math.min(ret, discovered[there]);
            }
        }

        if (ret == discovered[here]) {
            SCC scc = new SCC(sccCounter);

            while (true) {
                int t = stack.pop();
                sccId[t] = sccCounter;
                scc.vertexes.add(t);
                if (t == here) break;
            }

            sccList.add(scc);
            sccCounter++;
        }
        return ret;
    }


    static class SCC {
        final int id;
        final List<Integer> vertexes = new ArrayList<>();
        final List<SCC> link = new ArrayList<>();

        int inDegree = 0;

        public SCC(int id) {
            this.id = id;
        }
    }
}

 

깨달은 점

SCC를 응용한 문제를 풀어보면서 어떤 상황에서 사용하는지 조금씩 감을 잡기 시작했다.