😶🌫️ 문제
문제를 풀기 위해서는 다리가 무너진 상태에서 서로 왕복할 수 있도록 다리를 연결해야 합니다. 이 문제는 그래프 이론과 합집합 찾기(Unifon-Find) 자료구조를 사용하여 해결할 수 있습니다.
🌿 풀이
Union-Find
Union-Find 는 대표적인 그래프 알고리즘 입니다. '서로소 집합(Disjoint-Set)' 알고리즘이라고도 부릅니다. 구체적으로 여러개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 입니다. 간단하게 알아볼게요.
1. Union
다음과 같이 6개의 노드가 서로 연결된 것 없이 존재하고 있습니다. 이때 1-2 노드를 선으로 연결해서 그룹으로 묶는 것을 Union 이라고 합니다.
2. Find
다음과 같이 노드들이 연결되어 있을 때 1-2-3 이 한 그룹, 4-5-6 이 한 그룹이 됩니다.
1-3 은 서로 선으로 연결된 상태는 아니지만, 중간에 2를 통해 연결된 것을 저희는 알 수 있죠.
근데 이걸 컴퓨터가 알게 하려면 어떻게 표현해 주면 좋을까요?
Parent 라는 배열을 이용하여 알려줄 수 있습니다.
Parent 는 쉽게 말하면 그룹의 리더입니다. 1-2-3 그룹의 리더가 1이라고 가정하면, 3의 리더는 1, 1의 리더는 1 자신 이기 때문에 같은 그룹이라는 것을 알 수 있어요.
3. Parent 랑 같이 보기
다시 아무 연결이 없는 노드 상태 입니다. 이럴 때는 자기 자신의 노드번호를 parent 로 가집니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
1-2를 연결하면 한 그룹으로 묶여 같은 부모를 가지게 됩니다. 주로 더 적은 숫자를 부모 노드로 가지도록 합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 번호 | 1 | 1 | 3 | 4 | 5 | 6 |
2-3을 이어줄게요.
2-3 중 적은 숫자를 부모 노드로 가지니까 3의 부모노드가 2가 됬습니다.
근데 2의 부모노드는 1이기 때문에 3 또한 부모노드를 1로 갖게끔 해줘야 하는데요.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 번호 | 1 | 1 | 2 | 4 | 5 | 6 |
findParent 재귀함수를 사용해서 루트 노드를 찾을 수 있게끔 합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 번호 | 1 | 1 | 1 | 4 | 5 | 6 |
최종으로 이렇게 연결 된다면 ??
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 번호 | 1 | 1 | 1 | 4 | 4 | 4 |
🤖 코드
# 부모 노드를 찾는 함수
def getParent(parent, x):
if parent[x] == x:
return x
else:
parent[x] = getParent(parent, parent[x])
return parent[x]
# 두 부모 노드를 합치는 함수
def unionParent(parent, i, j):
i = getParent(parent, i)
j = getParent(parent, j)
if i < j:
parent[j] = i
else:
parent[i] = j
# 같은 부모 노드를 가지는지 확인
def findParent(parent, i, j):
i = getParent(parent, i)
j = getParent(parent, j)
if (i == j):
return 1
return 0
N = int(input())
parent = [i for i in range(N+1)]
for _ in range(N - 2):
i, j = map(int, input().split())
unionParent(parent, i, j)
answer = []
for i in range(1, N+1): # 부서진 다리 찾기
if i == parent[i]:
answer.append(i)
print(*answer)
중간에 findParent 함수는 사용하지 않지만 알고리즘 공부하면서 넣었습니다.
부서진 다리를 찾는 과정은 서로 다른 그룹에 있는 노드를 찾아서 연결하는 과정입니다.
parent 배열을 for 문 돌리면서 자기 자신이 parent 인 두 값을 출력하도록 했습니다.
