[백준] 17352번 여러분의 다리가 되어 드리겠습니다! 파이썬 코드

코드1

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

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

def find(a, parent):
  if a != parent[a]: # 루트 노드가 아니라면 
    parent[a] = find(parent[a], parent) # 루트 노드를 찾을 때까지 순회
  return parent[a] # 루트 노드 반환

def union(a,b,parent): 
  a = find(a, parent)
  b = find(b, parent)
  if a < b: # 루트 노드가 작은 값에 큰 값을 붙인다
    parent[b] = a
  else:
    parent[a] = b

for _ in range(n-2): # 그래프 만들어 주는 과정
  x, y = map(int, input().split())
  union(x, y, node)

for i in range(1, n+1):
  for j in range(i+1, n+1):
    if find(i, node) != find(j, node): # 루트 노드 값이 다르면 출력 후 프로그램 종료
      print(i, j)
      exit(0)

코드 2

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

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

def find(a, parent):
  if a != parent[a]:
    parent[a] = find(parent[a], parent)
  return parent[a]

def union(a,b,parent):
  a = find(a, parent)
  b = find(b, parent)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

for _ in range(n-2):
  x, y = map(int, input().split())
  union(x, y, node)
result = []
for i in range(1, n+1):
  if i == find(i, node): # 루트 노드가 자기 자신이면 == 연결되어있지 않으면 
    result.append(i) # 출력할 값에 추가
print(*result)

위 코드와 아래 코드는 출력할 값을 찾는 방식이 다르다. union-find를 사용하면 해결할 수 있다.