[Python] BOJ(백준) 17352번 - 여러분의 다리가 되어 드리겠습니다!

1. 링크

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

2. 난이도(solved.ac 참고)

골드5

3. 풀이

	# https://www.acmicpc.net/problem/17352
	import sys
	f = sys.stdin.readline
	def find_parent(parent, x):
	if parent[x] != x:
	parent[x] = find_parent(parent, parent[x])
	return parent[x]
	def union_parent(parent, a, b):
	a = find_parent(parent, a)
	b = find_parent(parent, b)
	if a < b:
	parent[b] = a
	elif a > b:
	parent[a] = b
	else:
	return
	n = int(f())
	parent = [0] * (n+1)
	for i in range(1, n+1):
	parent[i] = i
	for i in range(n-2):
	a, b = map(int, f().split())
	union_parent(parent, a, b)
	result = []
	for i in range(1, n+1):
	result.append(find_parent(parent, i))
	for i in range(1, len(result)):
	if result[i-1] != result[i]:
	if result.count(result[i-1]) > result.count(result[i]):
	print(result[i-1], result[i])
	break
	else:
	print(result[i], result[i-1])
	break

view raw BOJ17352.py hosted with ❤ by GitHub

input값을 받은 것들이 속하는 집합을 만든다. a와 b를 input으로 받았다면 각 a와 b의 루트 노드를 찾아서(find_parent 함수로) 더 작은 값이 부모 노드가 되는 방식이다. 현재 문제에서는 다리 하나만 놓으면 모든 노드가 전부 연결이 되어 있는 상태이다. 즉, n개의 섬 중 단 하나의 부모 노드만 다르다는 것이다. 그 값을 찾아서 (n-1개의 섬의 부모 노드, 나머지 하나의 섬의 부모 노드)의 값을 출력해주면 되는 문제였다. 이렇게 출력하면 되는 이유는, 부모 노드끼리 연결함으로써 최종적으로 모든 섬에 다 갈 수가 있게 되기 때문이다.