BOJ_17352_여러분의 다리가 되어 드리겠습니다! (Java)

[Gold V] 여러분의 다리가 되어 드리겠습니다! - 17352

문제 링크

성능 요약

메모리: 83392 KB, 시간: 548 ms

분류

자료 구조, 분리 집합, 그래프 이론, 그래프 탐색

제출 일자

2025년 1월 7일 20:22:41

문제 설명

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

어제까지는 그랬다.

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

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

입력

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

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

출력

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

문제 풀이

보자마자 Union-find 문제라고 생각했다. 모든 점들을 묶으면 2개의 그룹이 생긴다고 생각했다. 그래서 집합으로 묶자고 결정했다. 예제 2를 보면 2라는 숫자만 주어지고 1 2 를 출력해줘야하기 때문에 예외처리해주었고 이를 생각하다보니

5
2 3
3 4
4 5

이면 1 이랑 다른점중 하나 2 이런식으로 출력해야하므로 난 입력받은 수 중 처음을 group1으로 하려했는데 이 때문에 틀렸음을 생각해냈고 무조건 1을 group1, 다른 그룹을 만나면 그 수를 group2로 선정했다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int N, p[];
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		
		if (N==2) {
			System.out.print("1 2");
			return;
		}
		p = new int[N+1];
		for(int i=1; i<=N; i++) {
			p[i] = i;
		}

		int group1=1, group2=0;
		
		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);
		}
		
		for(int i=2; i<=N; i++) {
	        if(find(i) != find(group1)) {
	            group2 = i;
	            break;
	        }
	    }
		
		bw.write(String.valueOf(group1) + " " + String.valueOf(group2));
		bw.flush();
		bw.close();
		br.close();
	}

	private void union(int x, int y) {
		int px = find(x);
		int py = find(y);
		if(px != py) {
			if(px < py) p[py] = px;
			else p[px] = py;
		}
	}
	
	private int find(int x) {
		if(p[x] != x) return p[x] = find(p[x]);
		return p[x];
	}
}