[Algo] 백준 17352 여러분의 다리가 되어 드리겠습니다 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/17352

메모리 : 127140KB

시간 : 656ms

언어 : Java 11

---

코드

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

public class Main {
    static int[] parent;

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<List<Integer>> island = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            island.add(new ArrayList<>());
        }
        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());
            island.get(a).add(b);
            island.get(b).add(a);
        }
        
        // 부모의 번호를 저장하는 배열
        parent = new int[N + 1];	
        // 자기자신을 부모로 가리키도록 초기화
        for (int i = 0; i <= N; i++) {
            parent[i] = i;
        }
        for (int i = 1; i <= N; i++) {
            for (int j : island.get(i)) {
                makeUnion(i, j);		
            }
        }
        int[] ans = new int[2];
        int idx = 0;
        for (int i = 1; i <= N; i++) {
            if (parent[i] == i) {  //자기 자신이 부모인 경우? 유니온에 속하지 못한 외딴 섬
                ans[idx++] = i;
            }
        }
        System.out.println(ans[0] + " " + ans[1]);

    }
	//두 섬을 같은 유니온에 묶어 준다
    private static void makeUnion(int x, int y) {
        if (parent[y] != parent[x]) {	//부모가 다른 경우? 한쪽으로 부모를 몰아줘야 한다
            x = getParent(x);	//각자의 루트 부모를 데려온다.
            y = getParent(y);	// x,y값을 바꿔주는 이유? 루트 부모도 다른 쪽에 붙을 수 있기 때문에
            if (x < y) {	//편의를 위해 부모의 번호가 쪽으로 몰아준다
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }
	//부모 찾아오기
    private static int getParent(int x) {
        if (parent[x] == x) {	//자기 자신이 부모인 경우? 루트부모이다
            return x;
        } else {
            return getParent(parent[x]);  //그렇지 않은 경우 재귀로 루트까지 내려간다
        }
    }
}

 

풀이

모든 섬은 연결되어 있었는데, 하나가 무너졌기 때문에 이제 다리는 두 유니온으로 구성되어 있다. 두 개의 유니온을 이어줄 다리 하나를 지어주면 된다. 따라서 각 다리의 소속 유니온을 구하기 위해 Union-Find 를 사용했다. 유니온을 모두 찾아준 후에는 유니온이 다른 다리 두 개를 출력하면 된다. 

오랜만에 풀어서 기억이 가물가물..