20955 - 민서의 응급 수술 (Java)

 

---

 

문제

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

 

풀이

유니온 파인드를 활용해서 쉽게 풀 수 있는 문제이다.

 

뉴런은 노드, 시냅스는 엣지로 표현한다.

 

우선 입력으로 들어오는 값들을 연결하되,

 

사이클이 발생하면 연결을 끊는 과정을 거쳐야하기 때문에 연산횟수에 1을 더해준다.

 

그렇게 입력값이 다 끝났다면, 그룹을 확인해서 몇번의 연결 연산을 더 해야하는지 계산해주면 된다.

 

예로 그룹이 3개로 나뉘어져있다면 2번의 연결 연산이 더 필요한것이다.

 

단 주의해야할점이 union find 를 사용하다보면 내가 속한 부모의 그룹을 가리키고 있기 때문에 그룹의 개수를 구할려면 find 연산으로 계산을 하던가, 아니면 최적화 작업을 거쳐서 그룹번호를 가질 수 있도록 설정해두어야 한다.

 

 

 

 

 

코드

import java.util.*;
import java.io.*;

public class Main {
    public static Integer[] parent;
    public void solution() throws Exception {
        int answer = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // Vertex & Edge
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        parent = new Integer[n + 1];

        // Initialize
        for(int i=0; i<n+1; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            // 부모가 다르다면 작은값을 부모로 갱신해준다.
            int v1Parent = find(v1);
            int v2Parent = find(v2);

            // 같다면 연결하지 않는다. ( = 연결을 끊는다 -> answer + 1)
            if (v1Parent == v2Parent) {
                answer++;
                continue;
            }

            // 다를 경우 -> 작은값의 부모로 선택한다.
            if (v1Parent <= v2Parent) {
                parent[v2Parent] = parent[v1Parent];
            }

            if (v1Parent > v2Parent) {
                parent[v1Parent] = parent[v2Parent];
            }

        }
        // 최적화 작업
        for(int i=1; i<n+1; i++) find(i);

        Set<Integer> set = new HashSet<>(Arrays.asList(parent));
        // 종류가 한개가 되기 위한 만큼 answer 에 더한다.
        answer += set.size() - 2;
        System.out.println(answer);

        // 모두 끝난다음에, 부모 개수 - 1 만큼 더해서 답을 도출한다. (find 횟수)
    }

    public int find(int x){
        if(parent[x] == x){
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기