[백준 JAVA] 4196 : 도미노

[백준 4196] 도미노 : https://www.acmicpc.net/problem/4196

---

문제 조건

 

도미노가 한쪽 방향으로만 넘어지기에 단방향 간선으로 표현되지만, 실제로는 우리가 원하는 방향(왼쪽 또는 오른쪽)으로 도미노를 밀어 넘어뜨릴 수 있다. 즉, 한 도미노가 넘어진 방향에 따라 연쇄 반응을 일으키는 관계가 결정되는데, 이때 도미노를 그래프로 나타내면 간선이 기본적으로 한 방향(진출 간선)만 표시된다. 하지만 만약 어떤 도미노가 한쪽 방향에서는 연쇄 반응을 일으키지 못한다면, 그 도미노의 반대쪽(진입 간선) 방향으로도 연쇄 반응을 고려할 수 있어야 한다.

그래서 DFS를 진행할 때, 상황에 따라 진출 간선과 진입 간선을 서로 뒤바꿔서 탐색할 수 있다는 뜻이다. 이는 단순히 양방향 그래프가 되는 것이 아니라, 상황에 따라 간선의 역할을 유연하게 해석할 수 있음을 의미한다.

 

---

문제 해결 방법

 

도미노의 연쇄 반응은 그래프의 강한 연결 요소(SCC)로 모델링할 수 있다. 한 도미노가 넘어지면, 같은 SCC에 속한 모든 도미노는 결국 함께 넘어지게 된다.

 

이때, SCC들 사이에는 단방향 연결(진출/진입 간선)이 형성되는데, 만약 어떤 SCC에 외부에서 들어오는 진입 간선이 없다면, 그 SCC는 독립적인 상태라고 볼 수 있다. 따라서 모든 도미노를 넘어뜨리려면, 외부 영향 없이 독립적으로 남는 SCC마다 최소 한 번씩 수동으로 도미노를 넘어뜨려야 하며, 이때 그 수가 수동으로 넘어뜨려야 하는 블록의 최소 개수가 된다.

 

---

코드

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class BJ4196 {

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(bufferedReader.readLine());

        while (tc-- > 0) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int N = Integer.parseInt(stringTokenizer.nextToken());
            int M = Integer.parseInt(stringTokenizer.nextToken());

            // 도미노의 특성
            List<List<Integer>> outGraph = new ArrayList<>();
            List<List<Integer>> inGraph = new ArrayList<>();

            for (int i = 0; i <= N; i++) {
                outGraph.add(new ArrayList<>());
                inGraph.add(new ArrayList<>());
            }

            while (M-- > 0) {
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                int x = Integer.parseInt(stringTokenizer.nextToken());
                int y = Integer.parseInt(stringTokenizer.nextToken());

                outGraph.get(x).add(y);
                inGraph.get(y).add(x);
            }

            List<List<Integer>> SCCs = findSCCs(N, outGraph, inGraph);

            // 각 도미노 블록들에게 SCC 번호를 매김
            int idx = 1;
            int[] sccIdx = new int[N + 1];
            for (List<Integer> scc : SCCs) {
                for (int v : scc) {
                    sccIdx[v] = idx;
                }
                idx++;
            }

            // 각 SCC들에게 진입 간선이 있는지 확인
            boolean[] hasIndegree = new boolean[idx];
            for (int i = 1; i <= N; i++) {
                for (int v : outGraph.get(i)) {
                    if (sccIdx[i] != sccIdx[v]) {
                        hasIndegree[sccIdx[v]] = true;
                    }
                }
            }

            // 진입 간선이 없다면 수동으로 넘어뜨려야 함
            int result = 0;
            for (int i = 1; i < idx; i++) {
                if (!hasIndegree[i]) {
                    result++;
                }
            }

            System.out.println(result);
        }
    }

    // DFS 2번으로 SCC 탐색 (코사라주 알고리즘)
    private static List<List<Integer>> findSCCs(int N, List<List<Integer>> outGraph, List<List<Integer>> inGraph) {
        Stack<Integer> reversePostorder = new Stack<>();
        boolean[] visited = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            dfs(outGraph, i, visited, reversePostorder);
        }

        visited = new boolean[N + 1];
        List<List<Integer>> SCCs = new ArrayList<>();

        while (!reversePostorder.isEmpty()) {
            List<Integer> SCC = new ArrayList<>();
            dfs(inGraph, reversePostorder.pop(), visited, SCC);
            if (SCC.isEmpty()) {
                continue;
            }
            SCCs.add(SCC);
        }

        return SCCs;
    }

    // 후위 순회의 결과의 역순을 저장
    private static void dfs(List<List<Integer>> outGraph, int curr, boolean[] visited, Stack<Integer> reversePostorder) {
        if (visited[curr]) {
            return;
        }
        visited[curr] = true;
        for (int next : outGraph.get(curr)) {
            dfs(outGraph, next, visited, reversePostorder);
        }
        reversePostorder.push(curr);
    }

    // SCC를 저장
    private static void dfs(List<List<Integer>> inGraph, int curr, boolean[] visited, List<Integer> SCC) {
        if (visited[curr]) {
            return;
        }
        visited[curr] = true;
        SCC.add(curr);

        for (int next : inGraph.get(curr)) {
            dfs(inGraph, next, visited, SCC);
        }
    }
}

 

---

마무리

 

SCC와 위상 정렬이라는 키워드를 통해 접근했기에 큰 시행착오 없이 문제를 해결할 수 있었지만, 만약 일반적인 DFS/BFS 탐색과 백트래킹을 활용했다면 기하급수적인 시간 복잡도로 인해 해결이 어려웠을 것이다.

 

그럼에도 불구하고 SCC를 구한 후, 그들 간의 진입 간선을 확인하는 과정은 까다로웠다.

각 도미노가 속한 SCC 번호를 매긴 후,
그래프에서 SCC 간의 연결 관계를 추적하고,
외부로부터 영향을 받지 않는 독립적인 SCC를 찾아,
최소 몇 개의 도미노를 직접 넘어뜨려야 하는지를 계산

 

역시 그래프는 재밌어