[백준 20955] 민서의 응급수술 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/20955

20955번: 민서의 응급 수술

 

문제

민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서는 놀라 자빠질 수밖에 없었다. 한 학생이 꾸벅꾸벅 졸다가 책상에 머리를 아주 세게 박았기 때문이다. 한시라도 수술이 시급한 상황, 민서는 의사가 되어 수술을 집도하기로 결심하였다.

사람의 뇌는 수백억 개의 뉴런으로 구성되며, 각 뉴런은 시냅스를 통하여 연결된다. 민서의 진찰 결과, 학생은 뇌 속의 일부 뉴런의 연결이 끊어져 잠이 든 것으로 확인되었다. 끊어진 시냅스만 복구된다면 학생은 잠에서 깨어나겠지만, 알다시피 민서는 컴퓨터공학과 교수이다.

민서는 끊어진 시냅스를 복구하는 대신 뇌 속의 모든 뉴런을 하나의 트리 형태로 연결해보고자 한다. 여기서 트리란 사이클이 존재하지 않는 연결 그래프를 의미한다.

민서는 손기술이 뛰어나기 때문에 다음과 같은 연산을 무한히 수행할 수 있다. 연결되지 않은 두 뉴런을 연결하거나 이미 연결된 두 뉴런의 연결을 끊는다.

뉴런의 연결 정보가 주어졌을 때, 모든 뉴런을 하나의 트리 형태로 연결하기 위하여 필요한 최소 연산 횟수를 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 뉴런의 개수 N과 시냅스의 개수 M이 주어진다.

이후 M개의 줄에 걸쳐 시냅스로 연결된 두 뉴런의 번호 u, v가 주어진다.

모든 입력은 공백으로 구분되어 주어진다.

 

출력

첫 번째 줄에 모든 뉴런을 트리 형태로 연결하기 위하여 필요한 최소 연산 횟수를 출력한다.

풀이

접근법

1. 트리는 사이클이 없는 그래프니까, 이미 연결된 것을 다시 연결하면 사이클이 생긴다. = union-find를 이용해서 구해주자
2. 연결을 입력 받으면서 이미 같은 집합이면 그 연결을 끊어주어야 하기 때문에 이 경우 ans를 늘려준다.
3. 모두 하나의 연결요소여야 한다면, 그냥 1과 union 했을 경우에 연결이 되면 다른 집합이라는 것이니까 합쳐주고 ans를 늘려준다.

 

코드

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

public class Main {
    private static int[] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());
        // 1. 트리는 사이클이 없는 그래프니까, 이미 연결된 것을 다시 연결하면 사이클이 생긴다. 
        // => union-find를 이용해서 구해주자
        parents = new int[N+1];
        for(int i=0;i<=N;i++) parents[i] = i;
        int ans = 0;
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            // 2. 연결을 입력 받으면서 이미 같은 집합이면 그 연결을 끊어주어야 하기 때문에
            // 이 경우 ans를 늘려준다.
            if (!union(u, v)) ans++;
        }
        // 3. 모두 하나의 연결요소여야 한다면, 그냥 1과 union 했을 경우에
        // 연결이 되면 다른 집합이라는 것이니까 합쳐주고 ans를 늘려준다.
        for(int i=2;i<=N;i++) {
            if (union(1, i)) ans++;
        }
        System.out.println(ans);

    }
    private static int findset(int x) {
        if (parents[x] == x) return x;
        else return parents[x] = findset(parents[x]);
    }

    private static boolean union(int x, int y) {
        int xr = findset(x);
        int yr = findset(y);
        if (xr == yr) return false;

        parents[yr] = xr;
        return true;
    }
}

 

10분정도 걸렸다.