[백준, Java] 17352번, 여러분의 다리가 되어 드리겠습니다! (Union-Find)

문제 링크

17532번: 여러분의 다리가 되어 드리겠습니다!

---

 

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 1 ~ N개의 섬이 존재하며, N-1개의 다리로 이어져서 어느 섬이든 다닐 수 있었다.

2. 1개의 다리가 무너져서, 왕복할 수 없는 두 섬이 발생하였다.

3. N-2개의 다리가 주어질 때 모두 왕복할 수 있도록 다리를 새로 놓아야 하는 두 섬을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. N개의 섬에서 나누어진 그룹 2개를 탐색합니다.

 

3. 탐색을 통해 얻은 2개의 그룹을 나타내는 섬의 번호를 결과로 출력합니다.

 

나누어진 섬의 그룹 탐색(Union-Find, 분리 집합)

 

5(N)개의 섬이 존재할 때 N-1개의 다리로 모든 다리가 왕복할 수 있다면 아래와 같이 모든 섬이 1개의 다리로 연결되어 있는 형태입니다.

 

즉, 여기서 다리가 1개가 무너졌다는 것은 2개의 그룹으로 나뉘어진다는 것을 알 수 있습니다.

즉, N-2개의 다리를 기준으로 2개의 그룹의 대표되는 섬에 대해서 다리를 연결하게 된다면 모두 왕복할 수 있게 됩니다.

 

예를 들어, 빨간색 그룹의 대표가 1이고, 파란색 그룹의 대표가 4일 때 연결하면 모두 왕복할 수 있게된다.

즉, 우리는 그룹에 대해서 구분할 수 있는 Union-Find(분리 집합)을 이용해서 2개의 그룹을 구성한 뒤의 각 그룹의 부모를 결과로 출력하면 됩니다.

 

각 그룹의 부모를 정하는 규칙은 저는 해당 그룹의 가장 작은 값으로 설정하였습니다.

 

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

예제입력 1.

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

 

[섬 구조]

 

 

2. N개의 섬에서 나누어진 그룹 2개를 탐색합니다.

 

초기 Union-Find의 부모(각 자신을 가리케기 됩니다.)

섬 번호	1	2	3	4
부모	1	2	3	4

 

각 다리에 대해서 연결된 그룹을 탐색합니다.

 

[1, 2]

 

부모 값 변경

섬 번호	1	2	3	4
부모	1	1	3	4

더 작은 섬을  부모로 진행하는 것으로 2번 섬의 부모는 1이 됩니다.

 

[1, 3]

부모 값 변경

섬 번호	1	2	3	4
부모	1	1	1	4

더 작은 섬을  부모로 진행하는 것으로 2번 섬의 부모는 1이 됩니다.

 

 

N-2개의 섬을 모두 탐색하였으므로 2개의 그룹을 탐색합니다.

 

{ 1, 2, 3 } = 1

 

{ 4 } = 4

 

3. 탐색을 통해 얻은 2개의 그룹을 나타내는 섬의 번호를 결과로 출력합니다.

 

2개의 그룹의 부모 섬 번호를 결과로 출력합니다.

 

1 4을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 섬의 다리 정보를 띄어쓰기 기준 나누었습니다.
• 각 다리의 정보로 union함수를 통해서 그룹을 구성합니다.
• 얻은 그룹의 부모 섬 2개를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• union함수는 2개의 섬을 하나의 그룹으로 묶습니다.
• find함수는 현재 속한 그룹의 부모를 반환합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.io.IOException;

public class Main {
    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));
        int n = Integer.parseInt(br.readLine());
        int[] union = new int[n+1];
        //섬 부모 기본 설정
        for(int i=1;i<=n;i++){
            union[i] = i;
        }
        StringTokenizer st;
        //다리 정보 입력 및 그룹 부모 설정
        for(int i=0;i<n-2;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            //그룹 부모 설정
            union(a, b, union);
        }
        List<Integer> groups = new ArrayList<>();
        boolean[] visited = new boolean[n+1];
        //그룹의 정보 조회
        for(int i=1;i<=n;i++){
            int parent = find(i, union);
            if(!visited[parent]){
                visited[parent] = true;
                groups.add(parent);
            }
        }
        //만들어진 2개의 그룹 부모 BufferedWriter 저장
        for(int group : groups){
            bw.write(String.valueOf(group));
            bw.write(" ");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //부모의 값을 찾는 함수(find)
    static int find(int a, int[] union){
        if(union[a] == a){
            return a;
        }
        return union[a] = find(union[a], union);
    }
    //2개의 섬을 하나의 그룹으로 묶는 함수(union)
    static void union(int a, int b, int[] union){
        int pa = find(a, union);
        int pb = find(b, union);
        if(pa > pb){
            union[pa] = pb;
        } else if (pa < pb) {
            union[pb] = pa;
        }
    }
}