[BOJ 1944] 복제 로봇

https://www.acmicpc.net/problem/1944

해당 문제의 경우 시작점과 키가 있는 지점간의 모든 거리를 구해두고 MST를 만들면 된다. 여기서 주의해야 할 점은 

1) S와 K에서만 복제가 가능하기 때문에 57번째 줄 처럼 각각의 거리를 구할 때 K나 S에 도달했을 때에도 Queue에 넣어줘야 한다.

2) 배열의 크기는  M이다 .... 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <stdio.h>
 
#define INF 1e9
typedef long long ll;
using namespace std;
 
int n,m,dist[555][555],posnum[555][555],parent[555];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
bool chk(int y, int x){
    return 0<y && y<=n && 0<x && x <=n;
}
char arr[555][555];
bool visit[555][555];
vector<pair<int,int>> v;
vector<pair<int,pair<int,int>>> vt;
 
void bfs(int yy,int xx){
    memset(visit,false,sizeof(visit));
    
    queue<pair<int,int>> q;
    q.push({yy,xx});
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dist[i][j] = INF;
        }
    }
    dist[yy][xx] = 0;
    
    while(!q.empty()){
        int yyy = q.front().first;
        int xxx = q.front().second;
        q.pop();
        
        if(visit[yyy][xxx])continue;
        visit[yyy][xxx] = true;
        
        for(int i=0;i<4;i++){
            int y= yyy+dy[i];
            int x = xxx+dx[i];
            if(chk(y,x)){
                if(arr[y][x] == '0' && dist[y][x] >dist[yyy][xxx]+1){
                    dist[y][x] = dist[yyy][xxx]+1;
                    q.push({y,x});
                }else if((arr[y][x] == 'K' || arr[y][x] == 'S' )&& dist[y][x] == INF){
                    dist[y][x] = dist[yyy][xxx] +1;
                    q.push({y,x});
                }
            }
        }
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(arr[i][j] == 'S' || arr[i][j] == 'K'){
                if(dist[i][j] == INF){
                    cout << "-1"<<endl;
                    exit(0);
                }else{
                    vt.push_back({dist[i][j],{posnum[yy][xx],posnum[i][j]}});
                }
            }
        }
    }
}
 
int find(int x){
    if(x == parent[x])
        return x;
    else{
        return parent[x] = find(parent[x]);
    }
}
 
void merge(int x, int y){
    x = find(x);
    y = find(y);
    parent[x] = y;
}
void init(){
    for(int i=0;i<=m;i++){
        parent[i] = i;
    }
}
 
int main(){
    memset(visit,false,sizeof(visit));
    memset(posnum,0,sizeof(posnum));
    cin >> n >>m;
    init();
    
    int tmp = 1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> arr[i][j];
            if(arr[i][j] == 'K' || arr[i][j] == 'S'){
                posnum[i][j] = tmp;
                tmp++;
                v.push_back({i,j});
            }
        }
    }
    
    for(int i=0;i<v.size();i++){
        int yy = v[i].first;
        int xx = v[i].second;
        bfs(yy,xx);
    }
    sort(vt.begin(),vt.end());
    
    int ans = 0;
    for(int i=0;i<vt.size();i++){
        auto p = vt[i];
        int x = find(p.second.first);
        int y = find(p.second.second);
        if(x!= y){
            merge(x,y);
            ans += p.first;
        }
    }
    cout <<ans <<endl;
    return 0;
    
}