[백준]1944 복제로봇 #MST

1. 풀이

시작점, 열쇠가 있는 모든 지점에서 로봇이 복제되고,

모든 열쇠를 얻어야 하며, 이때 모든 로봇의 이동거리를 구한다.

위의 문제가 MST문제임을 알면 구현은 매우쉽게 일반적인 MST를 푸는것과 같이 하면 된다. 

하지만 위의 문제 MST문제인지를 알기가 어렵다. 따라서 조건을 어느정도 외워두고 비슷한 상황에서 MST를 떠올릴 줄 아는것이 중요해 보인다!

 

2. 소스코드

from collections import deque
import sys

dR=[0,0,-1,1]
dC=[1,-1,0,0]
N,M=map(int,input().split())

L=[]
for i in range(N):
    L.append(list(input()))

def dist(sR,sC,fR,fC):
    q=deque([[sR,sC]])
    visited=[[0 for j in range(N)] for i in range(N)]
    while(q):
        r,c=q.popleft()
        if r==fR and c==fC:
            return visited[r][c]
        for k in range(4):
            tempR=r+dR[k]
            tempC=c+dC[k]
            if 0<=tempR<N and 0<=tempC<N and visited[tempR][tempC]==0 and L[tempR][tempC]!="1":
                visited[tempR][tempC]=visited[r][c]+1
                q.append([tempR,tempC])
    return -1

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

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

loc=[]
for i in range(N):
    for j in range(N):
        if L[i][j]=="S" or L[i][j]=="K":
            loc.append([i,j])

parent=[i for i in range(M+1)]
edge=[]
for i in range(M+1):
    for j in range(i+1,M+1):
       d=dist(loc[i][0],loc[i][1],loc[j][0],loc[j][1])
       if d==-1:
           print(-1)
           sys.exit(1)
       edge.append([d,i,j])
edge.sort()
size=len(edge)

ans=0
cnt=0
for i in range(size):
    cost,a,b=edge[i]
    if find(a)!=find(b):
        union(a,b)
        cnt+=1
        ans+=cost
    if cnt==M:
        break
print(ans)