[파이썬] 백준 17352 : 여러분의 다리가 되어 드리겠습니다! (골드5)

[파이썬] 백준 17352 : 여러분의 다리가 되어 드리겠습니다! (골드5)

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

---

문제

---

풀이

방향성 생각

• 덩어리가 두개라서 아무 점에서 BFS를 돌린다.
• 1번에서 BFS를 돌린다 치고, 2~n까지 원소들을 방문할 때 마다 visit에서 제거해준다.
• 1번과 visit 내 임의의 원소를 출력

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())

graph = [[] for _ in range(n+1)]
for _ in range(n-2):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
visit = set(range(2,n+1))

q = deque([1])
while q:
    x = q.popleft()
    
    for nx in graph[x]:
        if nx in visit:
            visit.remove(nx)
            q.append(nx)
print(1,visit.pop())

 

코멘트

분리집합이라 재귀로 부모 지정해주고 그런거 생각하고 왔는데, 그냥 BFS.......