[JAVA] 백준 20955번 【G4.민서의 응급 수술】

문제

20955번: 민서의 응급 수술

 

풀이

1️⃣ 트리의 특징과 bfs 를 이용한 풀이

💡 떠오른 Idea

이 문제는, 무작위로 주어지는 노드간의 관계를 트리관계로 풀어가야 하는 문제이다.

먼저, 생각할 수 있는 경우는 다음과 같다.

1. 정상적인 트리 형태를 이루고 있는 집합인 경우
2. 특정 노드 집합이 사이클을 이루고 있는 경우
3. 1번 혹은 2번 같은 집합이 연결되어있지 않고 떨어져 있는경우

그래서 모든 뉴런을 하나의 트리 형태로 연결하기 위한 횟수를 어떻게 구해야할까 고민했는데

먼저 1번 같은 집합의 경우 건드릴 것이 없다.

하지만 1번같은 집합이 n개가 있고 집합간에 연결이 되어있지 않으면 서로 연결이 필요하기 때문에 n-1번의 연산이 필요하다.

따라서, bfs를 통해서 서로 연결되어 있지 않은 집합의 개수를 세어준 후, 그 집합 개수 -1 번의 연산이 필요하다는 것을 알 수 있다.

2번 케이스의 경우 사이클을 이루고있다면, 사이클을 제거해주어야 하는데

트리의 대표적인 특징 중 하나인, 트리 간선의 개수는 트리를 구성하는 (노드의 개수 -1) 개 라는 특징을 이용하여

특정 집합의 총 간선의 개수를 구한 후, (노드의 개수 -1)개로 만들어주기 위해 제거해야하는 간선의 수를 구함으로서 사이클을 제거하기 위한 횟수를 구할 수 있었다.

따라서, 각 집합이 몇개인지 구하고 각 집합이 이루는 간선의 개수를 구할 수 있다면 이 문제를 해결할 수 있다.

 

public class Main {
    static List<List<Integer>> nodes;
    static boolean[] checked;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        nodes = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            nodes.add(new ArrayList<>());
        }
        
        // 간선 양방향 연결
        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            nodes.get(u).add(v);
            nodes.get(v).add(u);
        }

        checked = new boolean[N + 1];
        int ans = 0;
        int cntOfGroup = 0;

        for (int i = 1; i < N + 1; i++) {
            if (!checked[i]) {
                int[] result = bfs(i);
                ans += (result[1] - (result[0] - 1));
                cntOfGroup++;
            }
        }
        
        ans += cntOfGroup - 1;
        System.out.println(ans);
    }

    private static int[] bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        checked[start] = true;

        int cntOfEdge = 0;
        int cntOfNode = 0;

        while (!q.isEmpty()) {
            int poll = q.poll();
            cntOfNode++;
            for (int connect : nodes.get(poll)) {
                if (!checked[connect]) {
                    checked[connect] = true;
                    q.offer(connect);
                }
            }
            cntOfEdge += nodes.get(poll).size();
        }
        // 간선을 양방향이라 가정하고 개수를 구하고 나누기 2를 하면 간선의 개수가 된다.
        return new int[]{cntOfNode, cntOfEdge/2};
    }

}

결과