[PS] 백준 17352 - 여러분의 다리가 되어 드리겠습니다!

문제

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

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

 

해설

 

이 문제는 DFS와 Disjoint-Set 두가지 방법으로 풀 수 있는 문제입니다. 이번 포스팅에서는 Disjoint-Set을 이용하여 문제를 해결해 보도록 하고 추후에 DFS 코드도 같이 업로드 하겠습니다.

 

문제에서 주어진 조건을 살펴보면 다음과 같습니다. 

 

1. N개의 섬들을 연결하는 다리가 N-1개 존재한다. 

 

2. N-1개의 다리 중 하나를 끊어버렸다.

 

3. N-2개의 연결된 다리가 주어졌을 때 모든 섬들 사이에 이동이 가능하도록 다리로 이을 두 섬의 번호를 구하라

 

이 문제는 결국 모든 정점을 연결하는 신장트리를 만드는 문제로 볼 수 있습니다.

 

주어진 N-2개의 연결된 입력 정보를 가지고 Union 연산을 통해 하나의 그룹으로 구성하고, 임의의 정점 한개를 선택하여, 편의상 1번 정점을 선택하도록 하겠습니다. 나머지 정점들과 그룹이 같은지 확인하는 과정을 거쳐 그룹이 같지 않은 정점을 찾아낼 때 까지 탐색을 수행하면 이 문제를 해결할 수 있습니다.

 

코드

 

/**
* 알고리즘 : Disjoint-Set, Union-Find
* 1. 일반적인 Union-Find 문제이다. 
* 2. 먼저 입력으로 주어진 n-2개의 정보들에 대해 union 연산을 수행한다음
* 3. 임의의 정점 한개를 잡아서 (이 코드에서는 1을 임의의 정점으로 설정)
* 4. n개의 정점들에 대해서 union 할 필요가 있는지 여부를 검사하고 
* 5. 만약 부모노드가 달라서 union 할 필요가 있는 경우 
* 6. 임의의 시작 정점과 해당 정점을 정답으로 하여 출력한다.
*
*/
public class BOJ_17352_여러분의_다리가_되어_드리겠습니다 {
	static StringBuilder sb = new StringBuilder();
	static int n;
	static int[] group;
	
	static int find(int u) {
		if(group[u] < 0) return u;
		return group[u] = find(group[u]);
	}
	
	static boolean union(int u, int v) { 
		u = find(u); v = find(v);
		if(u == v) return false;
		group[v] = u;
		return true;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		group = new int[n + 1];
		Arrays.fill(group, -1);
		
		// 주어진 입력에 대하여 union을 수행한다. 
		for(int i = 0; i<n-2; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			union(u, v);
		}
		
		// 임의의 정점 1로부터 나머지 정점들의 관계를 검사한다.
		for(int i = 2; i<=n; i++) {
			// 임의의 정점1과 같은 집합에 속해있지 않은 정점을 찾으면 종료
			if(union(1, i)) {
				sb.append(1).append(' ').append(i);
				break;
			}
		}
		System.out.println(sb);
	}
}