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

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

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

 

상호 배타적 집합(Disjoint Set), 즉 Union-Find 알고리즘을 이용하여 푸는 문제이다.

 

가장 기본적인 형태로 구현했는데 계속 시간초과가 나길래 find_p(x) 부분에서 경로압축으로 시간단축을 할 수 있도록 해주었다. 1-2-3 이렇게 연결되어 있을 경우 각각의 parent 리스트는 1, 1, 2 를 가리키고 있는데 경로압축을 이용하면 각각의 parent 리스트가 모두 1을 가리키므로 더 빠르게 부모 노드를 찾을 수 있다.

 

그래도 python은 계속 시간초과가 나서 rank도 도입했는데 더 시간이 오래걸리길래 빼고 계속 궁리했는데.... 그냥 input=sys.stdin.readline으로 입력받는 시간을 단축시켜주면 해결되는 거였다.. (^^;)

 

백준 input은 무조건 sys.stdin.readline으로 받는 습관을 기르자.... SWEA랑 번갈아가면서 푸니까 계속 까먹게 된다.

import sys
input = sys.stdin.readline

def find_p(x):
    if p[x] != x:
        p[x] = find_p(p[x])
        return p[x]
    else:
        return x


n = int(input())
p = [i for i in range(n+1)]

for _ in range(n-2):
    i1, i2 = map(int, input().split())
    p1 = find_p(i1)
    p2 = find_p(i2)
    if p1 == p2:
        continue
    p[p1] = p2

ans_island = []
for i in range(1, n+1):
    if i == p[i]:
        ans_island.append(i)

print(*ans_island)