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

작성일 2024-10-28 Edited on 2024-11-30 In Algorithm , 백준 Views: Disqus:

문제

원문 링크 : https://www.acmicpc.net/problem/1944

세준이는 어느 날 획기적인 로봇을 한 개 개발하였다. 그 로봇은 복제 장치를 이용하면 자기 자신을 똑같은 로봇으로 원하는 개수만큼 복제시킬 수 있다. 세준이는 어느 날 이 로봇을 테스트하기 위하여 어떤 미로에 이 로봇을 풀어 놓았다. 이 로봇의 임무는 미로에 흩어진 열쇠들을 모두 찾는 것이다. 그리고 열쇠가 있는 곳들과 로봇이 출발하는 위치에 로봇이 복제할 수 있는 장치를 장착해 두었다.

N*N의 정사각형 미로와 M개의 흩어진 열쇠의 위치, 그리고 이 로봇의 시작 위치가 주어져 있을 때, 모든 열쇠를 찾으면서 로봇이 움직이는 횟수의 합을 최소로 하는 프로그램을 작성하여라. 로봇은 상하좌우 네 방향으로 움직이며, 로봇이 열쇠가 있는 위치에 도달했을 때 열쇠를 찾은 것으로 한다. (복제된 로봇이어도 상관없다) 하나의 칸에 동시에 여러 개의 로봇이 위치할 수 있으며, 로봇이 한 번 지나간 자리라도 다른 로봇 또는 자기 자신이 다시 지나갈 수 있다. 복제에는 시간이 들지 않으며, 로봇이 움직이는 횟수의 합은 분열된 로봇 각각이 움직인 횟수의 총 합을 말한다. 복제된 로봇이 열쇠를 모두 찾은 후 같은 위치로 모일 필요는 없다.

풀이 및 구현

문제를 요약해보면 시작 위치 S에서부터 열쇠가 있는 위치 K를 모두 들리는 최단 경로를 찾는 문제이다.

S와 K를 모두 정점으로 놓았을 때 각 정점에서 로봇이 분열할 수 있고, 하나의 로봇이라도 정점에 도착하면 되기 때문에 모든 정점을 최소 가중치로 연결하는 MST를 구하면 된다.

그래서 먼저 BFS를 이용해 그래프를 만들고, 그래프의 MST를 구하면 된다.

정점 정보는 map<pair<int, int>, int>>에서 x, y좌표를 넣으면 정점의 인덱스를 반환하게 했고, S = 0, K = 1, 2, 3, … 순으로 번호를 매겼다.

각 정점마다 BFS를 돌면서 다른 정점과 연결 상태를 확인했다.
정점과 연결이 되어있으면 그래프에 {도착노드, 거리} 형태로 저장을 한다.

이때 BFS를 모든 정점에 대해 돌기 때문에 단방향으로 저장을 했다.

// 그래프를 만든다.
void BFS(int sx, int sy) {
    int n = v[{sx, sy}];
    vector<vector<int>> visited(N, vector<int>(N));
    queue<tuple<int, int, int>> q;
    q.push({0, sx, sy});

    while (!q.empty()) {
        auto [cur_w, cur_x, cur_y] = q.front();
        q.pop();

        if (cur_x < 0 || cur_x >= N || cur_y < 0 || cur_y >= N) continue;
        if (m[cur_x][cur_y] == '1') continue;
        if (visited[cur_x][cur_y]) continue;

        visited[cur_x][cur_y] = 1;

        // 정점에 도착했을 때
        if (m[cur_x][cur_y] == 'S' || m[cur_x][cur_y] == 'K') {
            if (cur_w) {
                auto m = v[{cur_x, cur_y}];
                adj[n].push_back({m, cur_w});
            }
        }

        for (int i = 0; i < 4; i++) {
            int nxt_x = cur_x + dx[i];
            int nxt_y = cur_y + dy[i];
            int nxt_w = cur_w + 1;
            q.push({nxt_w, nxt_x, nxt_y});
        }
    }
}

그래프가 완성이 되면 Prim 알고리즘을 통해 MST를 만들었다.

모든 열쇠를 찾는게 불가능 할 경우 -1을 반환해야 하므로 거리가 INF인 가중치가 있을 때는 -1을 반환해주고 그게 아니라면 가중치의 합을 모두 계산해 합을 반환해주었다.

// 만들어진 MST로 최소 이동 거리를 계산한다.
int Prim() {
    vector<int> d(M + 1, INF);
    priority_queue<pair<int, int>> pq;
    pq.push({0, 0});
    int cnt = 0;

    while (!pq.empty()) {
        auto [cur_w, cur_n] = pq.top();
        cur_w = -cur_w;
        pq.pop();

        if (d[cur_n] != INF) continue;
        d[cur_n] = cur_w;
        if (++cnt == M + 1) break;

        for (auto& [nxt_n, nxt_w] : adj[cur_n]) {
            pq.push({-nxt_w, nxt_n});
        }
    }

    int sum = 0;
    for (auto i : d) {
        
        // 모든 열쇠를 찾을 수 없기 때문에 -1을 반환한다.
        if (i == INF) return -1;
        sum += i;
    }
    return sum;
}

코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
#define INF (int) 1e9
using namespace std;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

int N, M;
vector<string> m;
map<pair<int, int>, int> v;
vector<vector<pair<int, int>>> adj;

void BFS(int sx, int sy) {
    int n = v[{sx, sy}];
    vector<vector<int>> visited(N, vector<int>(N));
    queue<tuple<int, int, int>> q;
    q.push({0, sx, sy});
    while (!q.empty()) {
        auto [cur_w, cur_x, cur_y] = q.front();
        q.pop();

        if (cur_x < 0 || cur_x >= N || cur_y < 0 || cur_y >= N) continue;
        if (m[cur_x][cur_y] == '1') continue;
        if (visited[cur_x][cur_y]) continue;

        visited[cur_x][cur_y] = 1;
        if (m[cur_x][cur_y] == 'S' || m[cur_x][cur_y] == 'K') {
            if (cur_w) {
                auto m = v[{cur_x, cur_y}];
                adj[n].push_back({m, cur_w});
            }
        }

        for (int i = 0; i < 4; i++) {
            int nxt_x = cur_x + dx[i];
            int nxt_y = cur_y + dy[i];
            int nxt_w = cur_w + 1;
            q.push({nxt_w, nxt_x, nxt_y});
        }
    }
}

int Prim() {
    vector<int> d(M + 1, INF);
    priority_queue<pair<int, int>> pq;
    pq.push({0, 0});
    int cnt = 0;

    while (!pq.empty()) {
        auto [cur_w, cur_n] = pq.top();
        cur_w = -cur_w;
        pq.pop();

        if (d[cur_n] != INF) continue;
        d[cur_n] = cur_w;
        if (++cnt == M + 1) break;

        for (auto& [nxt_n, nxt_w] : adj[cur_n]) {
            pq.push({-nxt_w, nxt_n});
        }
    }

    int sum = 0;
    for (auto i : d) {
        if (i == INF) return -1;
        sum += i;
    }
    return sum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> N >> M;
    m.assign(N, string());
    int vc = 1;

    for (int i = 0; i < N; i++) {
        cin >> m[i];

        for (int j = 0; j < N; j++) {
            if (m[i][j] == 'S') v.insert({{i, j}, 0});
            else if (m[i][j] == 'K') v.insert({{i, j}, vc++});
        }
    }
    adj.assign(M + 1, vector<pair<int, int>>());

    for (auto i : v) {
        BFS(i.first.first, i.first.second);
    }

    cout << Prim();
}

후기

미로의 크기 $N$의 범위가 $(4 \leq N \leq 50)$ 열쇠의 개수 $M$의 범위가 $(1 \leq M \leq 250)$이기 때문에 각 정점에 대해 모두 BFS를 돌더라도 시간이 여유로워 나이브하게 구현한 문제였다.

주어진 문제를 그래프를 변환하는 것이 번거롭긴 하지만 변환만 된다면 쉽게 풀 수 있는 문제라 생각한다.