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

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

https://www.acmicpc.net/problem/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)

from http://amaranth1ne.tistory.com/39 by ccl(A) rewrite - 2021-10-17 23:01:10