BOJ 1944(복제 로봇)풀이

solved.ac 티어 : 골드 2

 

S와 모든 K 간의 거리를 구해서 스패닝 트리를 구해주면 된다.

import sys
from collections import deque
sys.setrecursionlimit(10**9)
def find(a):
    if uf[a]<0:return a
    uf[a]=find(uf[a])
    return uf[a]
def merge(a,b):
    a=find(a)
    b=find(b)
    if a==b:return 0
    uf[b]=a
    return 1
def bfs(y,x,gt):
    pq=deque([[y,x,0]])
    ch=[[-1 for i in range(N)]for g in range(N)]
    ch[y][x]=0
    ny=0
    nx=0
    while pq!=deque([]):
        for i in range(4):
            nx=pq[0][1]+dx[i]
            ny=pq[0][0]+dy[i]
            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue
            if l[ny][nx]!="1"and ch[ny][nx]==-1:
                #print("#",ny,nx,ch[y][x])
                ch[ny][nx]=pq[0][2]+1
                #if l[ny][nx]=="K"or l[ny][nx]=="S":continue
                pq.append([ny,nx,pq[0][2]+1])
        pq.popleft()
    #for i in range(N):
    #    for g in range(N):
    #        print(ch[i][g],end=" ")
    #    print()
    
    #print(ch)
    #print(st)
    for i in range(M+1):
        if gt!=i:
            if ch[st[i][0]][st[i][1]]==-1:print(-1);sys.exit()
            e.append([ch[st[i][0]][st[i][1]],gt+1,i+1])
input=sys.stdin.readline
N,M=map(int,input().split())
l=[list(input().strip()) for i in range(N)]
st=[]
for i in range(N):
    for g in range(N):
        if l[i][g]=="S"or l[i][g]=="K":
            st.append([i,g])
dy=[-1,0,1,0]
dx=[0,1,0,-1]
e=[]
for i in range(M+1):
    bfs(st[i][0],st[i][1],i)
e.sort()
#print(e)
rt=0
cnt=0
uf=[-1]*(M+3)
for i in range(len(e)):
    if merge(e[i][1],e[i][2]):
        rt+=e[i][0]
        cnt+=1
        if cnt==M:break
print(rt)