백준 17352번 여러분의 다리가 되어 드리겠습니다!

문제

백준 17352번 여러분의 다리가 되어 드리겠습니다! 링크

전형적인 유니온 파인드 문제다. 유니온 파인드를 사용해서 풀었다.

풀이 방법

1. 대표노드 배열 생성하기

유니온 파인드는 대표노드 배열이 필요하다. 따라서 대표노드 배열을 N+1 길이로 생성해야한다.

2. 유니온 연산과 파인드 연산 구현하기

유니온 파인드 문제는 사실 유니온 연산과 파인드 연산을 구현하면 80프로는 끝난다. 따라서 유니온 연산과 파인드 연산을 구현해준다.

3. 첫 노드와 연결되어 있지 않은 노드를 찾아 출력하기

이 문제에서는 다리가 1개만 잘렸고, 어떤 노드끼리 연결할지는 아무거나 출력하라고 했으므로 기준을 첫번째 노드로 잡는다. 왜냐하면 결국 어딘가는 연결되어있지 않기 때문에 1번노드가 포함된 그룹과 1번노드가 포함되지 않은 그룹으로 나뉠 것이기 때문이다. 따라서 1번노드와 대표노드가 같지 않은 노드를 찾으면 해당 노드를 출력하고 종료한다.

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class p17352 {
    static int [] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); // 섬의 개수
        arr = new int[N+1];

        for(int i=1; i<N+1; i++) arr[i] = i;

        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);
        }

        int parent = find(1);
        sb.append(1).append(" ");
        for(int i=1; i<N+1; i++){
            if(find(i)!= parent){
                sb.append(i).append(" ");
                break;
            }
        }

        for(int i= 1; i<N+1; i++){
            arr[i] = find(i);
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    static void union(int a, int b){
        int aa = find(a);
        arr[aa] = find(b);
    }

    static int find(int num){
        if(arr[num]  == num) return num;
        return arr[num] = find(arr[num]);
    }
}