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

문제

N개의 섬이 존재하고 이들이 n-1개의 다리로 어떤 두 섬이든 이동할 수 있도록 연결되어 있다.

이때 다리 하나가 파괴되었고 새로운 다리를 연결해야할 때,

어떤 두 섬 사이에 다리를 연결하면 어떤 두 섬이든 이동할 수 있게 되는지 알아내는 문제이다.

풀이

• 이 문제에서 기존에 어떤 두 섬이든 이동할 수 있었다는 것은 모든 섬들이 하나의 집합을 이루고 있다는 뜻이다.
• 즉 모두 같은 부모 노드를 갖고 있다는 의미이다.

• 여기서 다리 하나가 없어졌다는 것은 1개의 집합이 끊어져 2개의 집합이 되었다는 것이다.

• 따라서 두 개의 집합의 섬(노드) 하나씩을 연결해주면 다시 1개의 집합으로 만들 수 있다.
• 즉, 두 집합의 부모 노드 끼리 연결해주면 되는 것이다.
• Union-Find 알고리즘을 사용해 두 개의 분리된 집합을 찾음으로써 답을 구할 수 있다.

Python 코드

# 입력 속도 개선
import sys
input = sys.stdin.readline

n = int(input())
parents = list(range(n+1)) # 부모 노드 저장

# 부모 노드 찾기
def find(x):
    if x == parents[x]:
        return x
    parents[x] = find(parents[x])
    return parents[x]

# 두 섬 중 작은 숫자를 기준으로 같은 부모를 갖게 함
def union(x,y):
    x = find(x)
    y = find(y)

    if x < y:
        parents[y] = x
    else:
        parents[x] = y

# 다리가 연결되어 있는 두 섬은 같은 부모를 갖게 함
for _ in range(n-2):
    island1, island2 = map(int,input().split())
    union(island1, island2)

# 1번 섬이 포함된 집합과 부모 노드가 다른 섬 찾아 정답 도출
# 작은 숫자가 부모 노드가 되도록 설정하였음으로 
# 1번이 1번이 포합된 집합의 부모 노드가 됨
for i in range(2,n+1):
    if find(1) != find(i):
        print(1,i)
        break

 

문제출처

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