[ 백준 ] 1944번 - 복제 로봇 (C++)

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

1944번: 복제 로봇

 

 

[ 문제풀이 ]

 

1. 미로를 입력받고, S와 K의 좌표에 번호를 붙입니다.

 

2. 2중 for문을 이용하여 S와 K의 모든 좌표들끼리 연결하고, edge 배열에 시작점과 도착점, 거리를 저장합니다.

 

3. edge 배열을 거리를 기준으로 오름차순으로 정렬합니다.

 

4. Union-Find를 이용하여 모든 노드를 연결하고, ans에 거리를 더합니다.

 

5. 위의 과정에서 노드를 연결할 때마다 cnt++ 해줍니다.

 

6. cnt == M일 경우 ans를 출력해 주고, 그렇지 않다면 -1을 출력해 줍니다.

 

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
struct node {
    int u;
    int v;
    int d;
};
 
bool cmp(node left, node right)
{
    return left.d < right.d;
}
 
int N, M;
char arr[51][51];
int check[251][251];
int key[51][51];
vector<node> edge;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int vect[251];
 
void getEdge(int y, int x)
{
    int u = key[y][x];
    int visited[50][50] = { 0 };
    queue<node> q;
    q.push({ y,x,0 });
    visited[y][x] = 1;
 
    while (!q.empty()) {
        const int y = q.front().u;
        const int x = q.front().v;
        const int cnt = q.front().d;
        q.pop();
 
        if ((arr[y][x] == 'S' || arr[y][x] == 'K') && cnt != 0) {
            int v = key[y][x];
            if (check[u][v] != 1 && check[v][u] != 1) {
                edge.push_back({ u,v,cnt });
                check[u][v] = 1;
                check[v][u] = 1;
            }
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy > 0 && yy < N - 1 && xx>0 && xx < N - 1) {
                if (arr[yy][xx] != '1' && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
}
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 1; i <= M; i++) {
        vect[i] = i;
    }
 
    int cnt = 1;
 
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            if (arr[i][j] == 'S') {
                key[i][j] = 0;
            }
            else if(arr[i][j] == 'K'){
                key[i][j] = cnt++;
            }
        }
    }
 
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            if (arr[i][j] == 'S' || arr[i][j] == 'K') {
                getEdge(i, j);
            }
        }
    }
 
    sort(edge.begin(), edge.end(), cmp);
 
    int ans = 0;
    cnt = 0;
 
    for (auto& next : edge) {
        const int u = next.u;
        const int v = next.v;
        const int d = next.d;
 
        if (Find(u) != Find(v)) {
            Union(u, v);
            ans += d;
            cnt++;
        }
    }
 
    if (cnt == M) {
        printf("%d", ans);
        return 0;
    }
 
    printf("-1");
}