백준 1944번 : 복제로봇 - BFS & Kruskal

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

1944번: 복제 로봇

1. 문제설명

BFS를 돌면서 모든 노드간 간선의 가중치를 구하고,

크루스칼을 시행하면된다.

 

이렇게 풀 수 있는 이유는 복제 로봇이 시작점, 키가 있는 곳에서 무한으로 복제가 가능하기 때문에

모든 노드를 이어놓고 최소스패닝트리를 구하면 답이 되기 때문이다.

 

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int N, M;
string arr[51];
int maze[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

struct Edge {
    int from, to, weight;
    bool operator<(const Edge &b) const {
        return weight < b.weight;
    }

};


vector<pair<int, int> > vertex;
vector<Edge> edge;

bool BFS(int num) {
    int x = vertex[num].first;
    int y = vertex[num].second;

    int check[51][51];
    memset(check, 0, sizeof(check));

    check[x][y] = 1;
    queue<pair<int, int> > Q;
    Q.push({x, y});

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (check[nx][ny] || maze[nx][ny] == -1) continue;
            check[nx][ny] = check[cur.first][cur.second] + 1;
            Q.push({nx, ny});
        }
    }

    for (int i = num + 1; i < vertex.size(); i++) {
        int nx = vertex[i].first;
        int ny = vertex[i].second;

        if (check[nx][ny] == 0) {
            return false;
        }
        edge.push_back({num, i, check[nx][ny] - 1});
    }


    return true;
}


//kruskal
int unf[3000];

int Find(int a) {
    if (unf[a] < 0) return a;
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a == b) return;
    if (unf[a] > unf[b]) {
        unf[b] += unf[a];
        unf[a] = b;
    } else {
        unf[a] += unf[b];
        unf[b] = a;
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    int kidx = 2;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == '1') {
                maze[i][j] = -1;
            } else if (arr[i][j] == 'S') {
                maze[i][j] = 1;
                vertex.push_back({i, j});
            } else if (arr[i][j] == 'K') {
                maze[i][j] = kidx++;
                vertex.push_back({i, j});
            }
        }
    }


    //각 노드간 edge 생성
    for (int i = 0; i < vertex.size() - 1; i++) {
        if (!BFS(i)) {
            //연결되지 않은 vertex 존재할 경우
            cout << -1 << '\n';
            return 0;
        }
    }


    //크루스칼
    int ans = 0;
    memset(unf, -1, sizeof(unf));
    sort(edge.begin(), edge.end());

    for (auto e: edge) {
        auto [a, b, c] = e;
        a = Find(a);
        b = Find(b);

        if (a != b) {
            Union(a, b);
            ans += c;
        }
    }
    cout << ans << '\n';
    
    return 0;
}