[실전 문제] 폭발물 설치

1. 문제

철수는 마을의 여러 건축물들을 폭파해달라는 요청을 받았다. 이에 건축물들을 하나씩 폭파하려 한다. 일반적으로, 하나의 건물을 폭파하기 위해서는 다이너마이트 하나가 필요하다고 하자. 철수의 마을에 있는 건축물들 사이에는 특별한 단방향 통로가 존재한다. 하나의 건축물을 폭파시킬 경우, 이 단방향 통로로 인하여 상황이 약간 복잡해지는데, 이는 건물 A에서 건물 B로 통로가 이어져 있을 경우, 건물 A를 폭파시키면 건물 B 역시 폭파된다는 것이다. 이유인 즉슨, 단방향 통로가 지하에 매설되어 있기 때문에, 지하의 통로가 무너지면서 건물 B가 함께 무너진다. 철수의 마을에 존재하는 건축물의 개수가 주어지고, 이 건축물들 사이의 단방향 통로가 주어질 때, 최소 몇 개의 다이너마이트가 있어야 모든 건축물을 폭파시킬 수 있는지를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 건축물의 개수 N이 주어지고, 단방향 통로의 개수 M이 주어진다.( 2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 단방향 통로의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 건축물 a에서 건축물 b로 향하는 단방향 통로가 존재한다는 의미이다. 각 정점의 번호는 1번부터 N번까지이다.

출력

모든 건축물을 폭파시키기 위해 필요한 최소의 다이너마이트 개수를 출력한다.

예제 입력

7 8
1 2
1 3
2 3
3 7
4 5
5 6
6 4
6 7

예제 출력

2

 

 

 

2. 풀이

이 문제는 코사라주 알고리즘으로 해결할 수 있다. 단, 이 경우에는 간선의 방향을 뒤집어서는 안된다.

만약 간선의 방향을 뒤집어서 문제에 접근한다면 그룹은 총 5개로 나뉘게 된다.

따라서 간선의 방향을 뒤집지 않고 역순으로 노드를 탐색해야 문제를 해결할 수 있다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

class Graph {

    private ArrayList<ArrayList<Integer>> graph;

    public Graph(int nodeSize) {
        graph = new ArrayList<>();

        for(int i = 0; i < nodeSize + 1; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public void put(int n, int m) {
        graph.get(n).add(m);
//        graph.get(m).add(n);
    }

    public ArrayList<Integer> getNode(int n) {
        return graph.get(n);
    }
}

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int m;

    private static Graph dirgraph;
    private static boolean[] isVisited;
    private static Stack<Integer> stack;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dirgraph = new Graph(n);
        isVisited = new boolean[n + 1];
        stack = new Stack<>();

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            dirgraph.put(a, b);
        }

        for(int i = 1; i <= n; i++) {
            if(!isVisited[i]) dfs(i);
        }

        Arrays.fill(isVisited, false);

        int groupNum = 0;
        while(!stack.isEmpty()) {
            int v = stack.pop();

            if(!isVisited[v]) {
                rdfs(v, groupNum);
                groupNum++;
            }
        }

        bw.write(groupNum + "");
        br.close();
        bw.flush();
        bw.close();
    }

    private static void dfs(int v) {
        isVisited[v] = true;

        for(int i = 0; i < dirgraph.getNode(v).size(); i++) {
            int w = dirgraph.getNode(v).get(i);
            if(!isVisited[w]) dfs(w);
        }
        stack.push(v);
    }

    private static void rdfs(int v, int groupNum) {
        isVisited[v] = true;

        for(int i = 0; i < dirgraph.getNode(v).size(); i++) {
            int w = dirgraph.getNode(v).get(i);
            if(!isVisited[w]) rdfs(w, groupNum);
        }
    }

}