백준 17352 (여러분의 다리가 되어 드리겠습니다) - java

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

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

 

문제

선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다.

어제까지는 그랬다.

"왜 다리가 N - 1개밖에 없냐, 통행하기 불편하다"며 선린월드에 불만을 갖던 욱제가 다리 하나를 무너뜨렸다! 안 그래도 불편한 통행이 더 불편해졌다. 서로 왕복할 수 없는 섬들이 생겼기 때문이다. 일단 급한 대로 정부는 선린월드의 건축가를 고용해, 서로 다른 두 섬을 다리로 이어서 다시 어떤 두 섬 사이든 왕복할 수 있게 하라는 지시를 내렸다.

그런데 그 건축가가 당신이다! 안 그래도 천하제일 코딩대회에 참가하느라 바쁜데...

 

유형 : MST , Union - Find

 

접근 방식

• MST를 완성하기 위해 1개의 간선이 부족한 입력의 형태가 주어진다.
• 간선간의 가중치의 개념이 없기 때문에 완성 할 수 있는 아무 간선을 선택하면 된다.
• union - find 를 통해 부모의 정보를 저장한다.
  • 최종 형태에는 서로 다른 부모의 값이 단 2개만 존재하게 된다.
• 2개의 부모를 출력하면 된다. (해당 간선을 연결하면 되기 때문 !)

전체 코드

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

public class Main {
    static int n = 0;
    static int[] root;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());

        root = new int[n+1];
        for(int i=1;i<=n;i++){
            root[i] = i;
        }

        for(int i=1;i<=n-2;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            union(s,e);
        }

        int f = 0;
        int s = 0;

        for(int i=1;i<=n;i++){
            int tmp = find(i);

            if(f == 0){
                f = tmp;
            }

            else if(f != tmp && s == 0){
                s = tmp;
                break;
            }
        }

        System.out.println(f+" "+s);

        br.close();
    }

    static int find(int x){
        if(x == root[x])
            return x;

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;

        else{
            root[x] = y;
        }
    }
}