[백준 P17352] 여러분의 다리가 되어드리겠습니다! Java

P17352 여러분의 다리가 되어 드리겠습니다!

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

문제

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

어제까지는 그랬다.

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

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

입력값

첫 줄에 정수 N이 주어진다. (2 ≤ N ≤ 300,000)

그 다음 N - 2개의 줄에는 욱제가 무너뜨리지 않은 다리들이 잇는 두 섬의 번호가 주어진다.

4
1 2
1 3

2

5
1 2
2 3
4 5

출력값

다리로 이을 두 섬의 번호를 출력한다. 여러 가지 방법이 있을 경우 그 중 아무거나 한 방법만 출력한다.

1 4 ("4 1"이나 "2 4", "4 3" 등 가능한 정답은 많이 있지만, 아무거나 하나만 출력해야 한다.)

1 2

3 4

알고리즘

욱제가 왜 … 가만히 있는 다리를 무너뜨렸는지는 모르겠다..

원래는 모든 섬이 연결되어 있었고, 하나의 다리가 부서져 두 부분으로 나누어졌기 때문에 서로 다른 부분에 속한 하나의 섬들을 뽑아내어 연결하면 문제는 해결된다.

Union-Find 알고리즘을 사용했다. 섬의 숫자와 어떤 섬이 연결되어 있는지를 확인하여 Union 해주고, 연결이 끝난 이후에 find 값이 서로 다른 2개의 인덱스를 아무거나 출력하면 된다.

우선 섬들이 모두 떨어져있다고 가정하고 섬의 수 만큼 int 배열을 선언한 뒤, 자기 자신을 가리키게 한다.

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

이후에 Union을 통해서 입력받은 2개의 섬을 연결한다. 이때 find한 값이 큰 섬에, 작은 값을 대입한다.

for (int i = 1; i <= N - 2; i++) {
    st = new StringTokenizer(br.readLine());
    int from = Integer.parseInt(st.nextToken());
    int to = Integer.parseInt(st.nextToken());

    union(from, to);
}

모든 섬들의 연결관계를 입력하고 첫 번째 인덱스의 find 값과 다른 값이 나올 때 까지 인덱스를 1씩 증가시키며 find 값을 구한다. 원래 모든 섬이 연결되어 있었고, 하나의 다리가 끊어졌으므로 현재 섬은 무조건 두 부분으로 나누어져 있다. 따라서 첫 번째 인덱스와 다른 값이 발견되면 그 두 인덱스를 출력하면 된다.

int point1 = 1;
int point2 = point1;

for (int i = 2; i <= N; i++)
    if (point1 != find(parent[i])) {
        point2 = parent[i]; break;
    }

System.out.println(1 + " " + point2);

코드

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

public class Main {
    static int N;
    static int[] parent;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) parent[i] = i;

        for (int i = 1; i <= N - 2; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            union(from, to);
        }

        int point1 = 1;
        int point2 = point1;

        for (int i = 2; i <= N; i++)
            if (point1 != find(parent[i])) {
                point2 = parent[i]; break;
            }

        System.out.println(1 + " " + point2);
    }

    public static void union(int a , int b) {
        int aParent = find(a);
        int bParent = find(b);

        if (aParent < bParent) parent[bParent] = aParent;
        else parent[aParent] = bParent;
    }

    public static int find (int target) {
        if (parent[target] == target) return target;
        else return parent[target] = find(parent[target]);
    }
}