0부터 n-1까지 번호가 매겨진 n개의 정점으로 이루어진 무방향 그래프가 주어졌다고 가정해 보겠습니다. 그래프의 각 간선에는 가중치가 부여되어 있으며, 가중치는 세 가지 유형 중 하나로 각각 특정한 의미를 가집니다. 그래프를 탐색하는 사람은 Jack과 Casey 두 명입니다. Jack은 가중치가 1인 간선만 통과할 수 있고, Casey는 가중치가 2인 간선만 통과할 수 있으며, 가중치가 3인 간선은 두 사람 모두 통과할 수 있습니다. 우리의 목표는 불필요한 간선을 제거하여 두 사람 모두 그래프 전체를 탐색할 수 있도록 만드는 것입니다. 이때 제거해야 하는 간선의 개수를 반환하고, 아무리 간선을 제거해도 탐색이 불가능하다면 -1을 반환합니다.
예를 들어 입력이 다음과 같고,
n = 5라면 출력은 -1이 됩니다.
간선을 제거한다고 하더라도 두 사람 모두가 그래프를 완전히 탐색할 수 없기 때문입니다. 따라서 답은 -1입니다.
해결 접근 방법
이 문제는 유니온-파인드(Union-Find) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 가중치 3(공용) 간선을 우선 처리한 뒤, 각 사람의 전용 간선을 독립적으로 처리하는 것입니다. 다음 단계를 따릅니다.
find(val) 함수를 정의합니다.
val이 root[val]과 같지 않으면, root[val] := find(root[val])로 재귀적으로 갱신합니다(경로 압축).
root[val]을 반환합니다.
union(val1, val2) 함수를 정의합니다.
val1 := find(val1), val2 := find(val2)
val1과 val2가 같으면 이미 같은 집합에 속한 것이므로 0을 반환합니다.
root[val1] := val2로 두 집합을 병합하고 1을 반환합니다.
res := 0, edge1 := 0, edge2 := 0으로 초기화합니다.
root := 0부터 n+1까지의 값으로 이루어진 새 리스트를 생성합니다.
먼저 가중치 3(두 사람 모두 사용 가능)인 간선들을 순회하며 처리합니다.
union(v, w)의 결과가 0이 아니면(병합 성공), edge1과 edge2를 각각 1씩 증가시킵니다.
그렇지 않으면(이미 연결됨), 해당 간선은 불필요하므로 res := res + 1로 제거 대상에 포함합니다.
root0 := root의 복사본을 저장해 둡니다.
다음으로 가중치 1(Jack 전용)인 간선들을 순회하며 처리합니다.
union(v, w)의 결과가 0이 아니면 edge1을 1 증가시킵니다.
그렇지 않으면 res := res + 1로 제거 대상에 포함합니다.
root := root0으로 상태를 복원한 뒤, 가중치 2(Casey 전용)인 간선들을 순회하며 처리합니다.
union(v, w)의 결과가 0이 아니면 edge2를 1 증가시킵니다.
그렇지 않으면 res := res + 1로 제거 대상에 포함합니다.
edge1 == edge2 == n - 1이면 두 사람 모두 그래프 전체를 탐색할 수 있는 것이므로 res를 반환합니다.
그렇지 않으면 -1을 반환합니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
def solve(n, e):
def find(val):
if val != root[val]:
root[val] = find(root[val])
return root[val]
def union(val1, val2):
val1, val2 = find(val1), find(val2)
if val1 == val2: return 0
root[val1] = val2
return 1
res = edge1 = edge2 = 0
root = list(range(n + 1))
for u, v, w in e:
if u == 3:
if union(v, w):
edge1 += 1
edge2 += 1
else:
res += 1
root0 = root[:]
for u, v, w in e:
if u == 1:
if union(v, w):
edge1 += 1
else:
res += 1
root = root0
for u, v, w in e:
if u == 2:
if union(v, w):
edge2 += 1
else:
res += 1
return res if edge1 == edge2 == n - 1 else -1
print(solve(5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]))
입력
Input: 5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]
출력
-1