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

링크

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

난이도(solved.ac 참고)

골드5

풀이

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