[백준, Java] 20955번, 민서의 응급 수술(Union-Find)

문제 링크

20955번: 민서의 응급 수술

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 뉴런들에 대한 끊어진 시냅스를 연결해서 하나의 트리 형태(싸이클 X)로 연결하려고 합니다.

2. 민서는 두 뉴런을 연결하는 시냅스를 만들거나 이미 연결된 시냅스를 끊을 수 있습니다.

3. 뉴런을 하나의 트리 형태로 구성할 때 민서가 최소 행동 횟수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. Union-Find을 통해서 사이클이 발생하지 않고 모두 연결된 뉴런을 만드는 횟수를 탐색합니다.

 

3. 탐색을 통해 민서가 작업한 횟수를 결과로 출력합니다.

 

 

뉴런 연결하기(Union-Find)

 

뉴런과 시냅스 정보가 주어졌을 때에 각 집합이 구성됩니다.

 

주의해야 할 점 크게 2가지입니다.

 

1. 뉴런의 최종적인 형태는 트리 형태 = 사이클 X 가 되어야 한다는 것입니다.

 

즉, 집합을 만드는 과정에서 동일한 집합을 바라보게 된다는 것은 사이클이 형성된다는 것입니다.

 

→ Union-Find에서 Union을 진행할 때 2개의 부모 값이 동일할 때 사이클이 존재한다.

 

Union과정에서 사이클 발생이 생긴 경우 해당 시냅스를 제거해서 사이클 형성을 막아야 하는 것입니다.

 

2. Union-Find을 진행한 이후에는 각 집합들을 하나의 트리로 만들기 위해서 시냅스로 연결을 진행해주어야 합니다.

 

이미 Union을 통해서 사이클이 생기지 않는 집합들이기 때문에 n개의 집합이 존재하면 n-1개의 시냅스로 연결해주면 트리 형태 구현됩니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N(뉴런 개수)	M(이미 연결된 시냅스 개수)
4	2

 

 뉴런 및 시냅스 상태

 

 

 

2. Union-Find을 통해서 사이클이 발생하지 않고 모두 연결된 뉴런을 만드는 횟수를 탐색합니다.

 

Union-Find을 진행하기 앞서 각 뉴런에 부모를 정해주는 작업을 진행합니다.(MakeSet)

 

뉴런	1	2	3	4
부모	1	2	3	4

 

 

사이클이 생성되는 것을 확인하며 각 시냅스에 맞게 Union-Find진행

 

1 - 2

 

 

뉴런	1	2	3	4
부모	1	1	3	4

 

 

 

뉴런 1 부모 : 1

 

뉴런 2 부모 : 2

 

동일하지 않으므로 사이클 발생 X이며 시냅스로 연결 완료!

 

3 - 4

 

뉴런	1	2	3	4
부모	1	1	3	3

뉴런 3 부모 : 3

 

뉴런 4 부모 : 4

 

동일하지 않으므로 사이클 발생 X이며 시냅스로 연결 완료!

 

 

집합 완성 이후 각 집합을 연결하는 시냅스 연결!

 

집합의 개수 : 2개

 

연결할 시냅스의 개수 : 집합의 개수 - 1 = 2 - 1 = 1개

 

 

 

3. 탐색을 통해 민서가 작업한 횟수를 결과로 출력합니다.

 

사이클 생성으로 시냅스를 끊어낸 횟수 : 0번

 

각 집합을 연결하는 시냅스를 진행한 횟수 : 1번

 

민서가 총 작업한 횟수 : 0 + 1 = 1번

 

1 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 뉴런 및 시냅스 정보를 띄어쓰기 기준 나누었습니다.
• for문으로 Union-Find 진행 전 부모를 정하는 MakeSet을 진행하였습니다.
• M개의 시냅스에 대해서 Union-Find을 진행하여 집합을 형성하였습니다.
• 집합 형성시 사이클이 생성되면 끊는 시냅스 작업 횟수를 증가시켰습니다.
• 만들어진 집합에 대해서 시냅스를 연결하여 1개의 트리 형태로 만들었습니다.
• 탐색을 통해 민서의 작업 횟수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• find 함수는 Union-Find에서 부모를 찾는 과정을 진행합니다.
• union 함수는 Union-Find에서 두 부모를 합치는 과정을 진행합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    //분리 집합 부모 정보 저장하는 배열
    static int[] parents;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int neurons = Integer.parseInt(st.nextToken());
        int synapse = Integer.parseInt(st.nextToken());
        parents = new int[neurons+1];
        //Union-Find MakeSet
        for(int i=1;i<=neurons;i++){
            parents[i] = i;
        }
        int result = 0;
        //Union-Find 분리 집합을 통한 집합 개수 구하기
        for(int i=0;i<synapse;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            //true : 사이클 발생 = 사이클 발생 시냅스 끊는 작업 진행
            if(union(a, b)){
                result++;
            }
        }
        Set<Integer> set = new HashSet<>();
        //집합의 개수 구하기
        for(int i=1;i<=neurons;i++){
            int parent = find(i);
            set.add(parent);
        }
        //모든 집합들 시냅스 연결하기
        result += set.size()-1;
        //최소 행동한 횟수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //Union-Find Find Method(부모 찾기)
    static int find(int a){
        if(parents[a] == a){
            return a;
        }
        return parents[a] = find(parents[a]);
    }
    //Union-Find Union Method(부모 비교 후 합치기)
    static boolean union(int a, int b){
        int pa = find(a);
        int pb = find(b);
        if(pa == pb){
            return true;
        }
        //부모가 작은 값이 부모가 되도록
        if(pb < pa){
            parents[pa] = pb;
        }else{
            parents[pb] = pa;
        }
        return false;
    }
}