[Python 3] BOJ 23743 방탈출

 

굉장히 재밌게 풀었던 MST 문제였다. 방들끼리의 연결 관계가 주어져있고, 이들 사이에 워프를 만들 수 있는 시간이 주어져 있다. 또한, 바로 밖으로 나갈 수 있는 긴급 탈출구 설치에 걸리는 시간이 주어져 있다. 이들을 단순히 "두 점 사이의 간선의 길이"라고 표현하겠다. 

 

이 문제의 예제 입력의 상황을 그림으로 표현해보겠다.

첫 번째 예제이다. 1번, 2번, 3번 긴급 탈출로 탈출하는 것 보다, 세 개의 간선 (1-2, 2-3, 3-1) 중 두 개를 선택하고, 3 정점 중 한 개의 긴급탈출을 만들어서 탈출하면 총 7의 minimum cost가 발생한다.

 

이 경우에는 1과 2 사이에 있는 간선을 선택하고, 1과 2의 정점 중 한 개의 비상탈출구를 만든다. 3은 탈출 할 수 있는 방법이 없기 때문에, 무조건 비상탈출구를 만들어야한다. 총 8의 minimum cost가 든다.

 

하지만, 이런 경우도 있다. 만약 방들끼리 연결되는 cost가 매우 크고, 비상 탈출구로 빠져나가는게 오히려 길이가 짧아서 결국 비상탈출구가 우선적으로 제작되어야하는 경우도 있다. 

 

결국, 출구 또한 한개의 정점으로 생각하기로 했다. (0번째)

그리고 모두를 최적의 cost로 잇는 MST 알고리즘 중 크루스칼 알고리즘을 사용하기로 했다.

 

 

n,m=map(int,input().split())
data=list()
for _ in range(m):
    a,b,c=map(int,input().split())
    data.append([c,a,b])

parents=[i for i in range(n+1)]
def find(a):
    if a!=parents[a]:
        parents[a]=find(parents[a])
    return parents[a]

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

val=list(map(int,input().split()))
for i in range(1,n+1):
    data.append([val[i-1],i,0])

data.sort()
answer=0

for i in range(len(data)):
    c,a,b=data[i]
    if find(a)!=find(b):
        union(a,b)
        answer+=c

print(answer)

 

크루스칼 알고리즘은 union-find 알고리즘을 사용한 MST 알고리즘이다. 둘 사이의 정점을 모두 받아서, 제일 작은 것부터 큰 걸로 sort한다. 간선들을 union할 때, 이미 둘 사이의 연결고리가 있으면 더 연결할 필요가 없기 때문에 (cycle이 만들어지기 때문에) 그냥 지나가고, 둘 사이의 연결 고리가 없으면 find함수를 통해 연결한다.

 

출구를 "0번째 방"으로 인식해서 푸는 아이디어가 중요했던 문제같다.