[백준 1944] 복제 로봇 C++

1944번: 복제 로봇

최소 스패닝 트리 - MST

---

현재 로봇이 복제를 거듭하며 열쇠를 찾으러 다니는 이동거리를 가장 작게 해야한다.

전체 이동거리를 가장 작게 해야하므로 다익스트라가 아니라 MST알고리즘을 사용해야 한다는걸 알았다.

 

입력을 받으면서 시작점과 모든 열쇠들은 정점이 되므로 정점 vector에 넣어준다.

 

정점들 간의 거리를 BFS를 통해 모두 구하고 간선의 정보를 저장한다.

BFS 매번 돌면 자신을 제외하고 시작점을 포함한(M-1+1) M번 만큼 다른 정점에 도달하게 된다.

이때 다른 정점에 M번 만큼 도달하지 못한다면 현재 정점과 아직 도달하지 못한 정점은 서로 연결 할 수 없으므로 -1을 출력한다.

그리고 BFS를 돌면서 현재 정점의 번호보다 높은 번호만 탐색하도록 했다. 현재 번호보다 낮은 번호의 정점들은 이미 현재 정점과의 간선의 정보를 저장했기 때문이다.

 

가상 정점을 만들어서 시작점과의 거리를 0으로 두어 시작점을 반드시 포함하게 만들었다.

 

가상 정점과 시작점과의 간선이 하나 추가되었으므로 전체 정점은 M+2가 된다.

따라서 MST 알고리즘을 수행하면서 간선의 개수가 M+1개가 되면 종료한다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
struct Line{
    int st, ed, val;
};
 
int N, M, St;
int Map[51][51], Node[255];
vector<pii > Vertax;
vector<Line> Edge;
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
map<pii, int> hmap;
 
bool cmp(Line &a, Line &b){
    return a.val < b.val;
}
 
int findtopnode(int a){
    if(Node[a] < 0) return a;
    return Node[a] = findtopnode(Node[a]);
}
 
bool Union_Node(int a, int b){
    a = findtopnode(a);
    b = findtopnode(b);
    if(a == b) return false;
    
    if(Node[a] < Node[b]){
        Node[a] += Node[b];
        Node[b] = a;
    }
    else{
        Node[b] += Node[a];
        Node[a] = b;
    }
    
    return true;
}
 
void input(){
    int i = 1;
    char b;
    string str;
    Vertax.push_back({0, 0});
    
    cin >> N >> M;
    
    for(int r = 0; r < N; r++){
        cin >> str;
        for(int c = 0; c < N; c++){
            b = str[c];
            switch (b){
            case '1': Map[r][c] = 0; break;
            case '0': Map[r][c] = 1; break;
            case 'S': 
                Vertax.push_back({r, c});
                St = i;
                hmap[{r, c}] = i++;
                Map[r][c] = 2;
                break;
            case 'K':
                Vertax.push_back({r, c});
                hmap[{r, c}] = i++;
                Map[r][c] = 2;
                break;
            default: break;
            }
        }
    }
    Edge.push_back({0, St, 0});
    memset(Node, -1, sizeof(Node));
}
 
bool BFS(int r, int c, int i){
    int cnt = -1;
    bool visited[51][51];
    memset(visited, 0, sizeof(visited));
    // 구조체 변수명이 안맞지만 그냥 씀.
    // st : r,  ed : c,  val : dist
    queue<Line> que;
    que.push({r, c, 0});
    visited[r][c] = true;
    
    while(!que.empty()){
        Line now = que.front();
        que.pop();
        
        if(Map[now.st][now.ed] == 2){
            cnt++;
            int idx = hmap[{now.st, now.ed}];
            if(idx > i){
                Edge.push_back({i, idx, now.val});
            }
        }
        
        for(int k = 0; k < 4; k++){
            int nr = now.st + dr[k];
            int nc = now.ed + dc[k];
            
            if(!Map[nr][nc] || visited[nr][nc]) continue;
            que.push({nr, nc, now.val+1});
            visited[nr][nc] = true;
        }
    }
    
    if(cnt == M) return true;
    return false;
}
 
void solve(){
    for(int i = 1; i <= M+1; i++){
        if(!BFS(Vertax[i].first, Vertax[i].second, i)){
            cout << -1 << "\n";
            return;
        }
    }
    
    int cnt = 0, ans = 0;
    
    sort(Edge.begin(), Edge.end(), cmp);
    
    for(int i = 1; i < Edge.size(); i++){
        int u = Edge[i].st;
        int v = Edge[i].ed;
        int dist = Edge[i].val;
        
        if(Union_Node(u, v)){
            cnt++;
            ans += dist;
        }
        if(cnt == M+1) break;
    }
    
    cout << ans << "\n";
}
 
int main(){
    input();
    solve();
    
    return 0;
}