문제

세준이는 어느 날 획기적인 로봇을 한 개 개발하였다. 그 로봇은 복제 장치를 이용하면 자기 자신을 똑같은 로봇으로 원하는 개수만큼 복제시킬 수 있다. 세준이는 어느 날 이 로봇을 테스트하기 위하여 어떤 미로에 이 로봇을 풀어 놓았다. 이 로봇의 임무는 미로에 흩어진 열쇠들을 모두 찾는 것이다. 그리고 열쇠가 있는 곳들과 로봇이 출발하는 위치에 로봇이 복제할 수 있는 장치를 장착해 두었다. N*N의 정사각형 미로와 M개의 흩어진 열쇠의 위치, 그리고 이 로봇의 시작 위치가 주어져 있을 때, 모든 열쇠를 찾으면서 로봇이 움직이는 횟수의 합을 최소로 하는 프로그램을 작성하여라. 로봇은 상하좌우 네 방향으로 움직이며, 로봇이 열쇠가 있는 위치에 도달했을 때 열쇠를 찾은 것으로 한다. (복제된 로봇이어도 상관없다) 하나의 칸에 동시에 여러 개의 로봇이 위치할 수 있으며, 로봇이 한 번 지나간 자리라도 다른 로봇 또는 자기 자신이 다시 지나갈 수 있다. 복제에는 시간이 들지 않으며, 로봇이 움직이는 횟수의 합은 분열된 로봇 각각이 움직인 횟수의 총 합을 말한다. 복제된 로봇이 열쇠를 모두 찾은 후 같은 위치로 모일 필요는 없다.

접근

최소신장트리와 너비우선탐색을 활용하여 풀었다. 로봇이 무제한으로 복제되어 이동할 수 있어 복제 지점들끼리 연결되기만 하면 되기에, 열쇠 위치들과 시작점 간의 최소신장트리를 만들면 된다. 최소신장트리를 만들기 위하여 각 복제지점간의 최소거리를 너비우선탐색을 통해 구했다. edges에 복제지점간의 거리를 가중치로 갖는 간선 정보를 집어넣고, 크루스칼 알고리즘을 통해서 최소신장트리를 완성했다. 전부 연결된것을 확인하기 위해 분리집합을 사용했다.

입력

첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어진다. 1은 미로의 벽을 의미하고, 0은 지나다닐 수 있는 길, S는 로봇이 출발하는 위치, K는 열쇠의 위치가 주어진다. S는 1개, K는 M개가 주어진다. S와 K에서만 복제를 할 수 있음에 유의한다. 미로는 벽으로 둘러쌓여 있는 형태이다. 즉, 모든 테두리는 벽이다.

출력

첫째 줄에 모든 로봇이 움직인 횟수의 총 합을 출력한다. 모든 열쇠를 찾는 것이 불가능한 경우 횟수 대신 첫째 줄에 -1을 출력하면 된다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef const ll cll;
typedef queue<ll> qll;
typedef queue<pll> qpll;
typedef priority_queue<ll> pqll;
typedef priority_queue<pll> pqpll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

cll N = 50, M = 250, directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
ll n, m, mat[N][N] = {{}}, parents[M] = {};
vll nodes;

bool isValid(ll i, ll l)
{
    return i >= 0 && i < n && l >= 0 && l < n && !mat[i][l];
}

ll find(ll i)
{
    if (parents[i] == i)
    {
        return i;
    }
    else
    {
        return parents[i] = find(parents[i]);
    }
}

void merge(ll i, ll l)
{
    parents[find(l)] = i;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (ll i = 0, key = 2; i < n; ++i)
    {
        cin.ignore();
        for (ll l = 0; l < n; ++l)
        {
            char c;
            cin >> c;
            switch (c)
            {
            case 'S':
            case 'K':
                nodes.emplace_back(i * n + l);
            default:
                mat[i][l] = c == '1';
            }
        }
    }

    priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq;
    for (ll idx = 0; idx < nodes.size(); ++idx)
    {
        ll node = nodes[idx], visited[N][N] = {{}};
        qll q;
        q.push(node);
        visited[node / n][node % n] = 1;
        while (!q.empty())
        {
            ll i = q.front() / n, l = q.front() % n;
            q.pop();
            for (auto &d : directions)
            {
                ll _i = i + d[0], _l = l + d[1], next = _i * n + _l;
                if (!isValid(_i, _l) || visited[_i][_l])
                {
                    continue;
                }
                q.push(next);
                visited[_i][_l] = visited[i][l] + 1;
            }
        }

        for (ll _idx = 0; _idx < nodes.size(); ++_idx)
        {
            ll _node = nodes[_idx], i = _node / n, l = _node % n;
            if (visited[i][l] > 1)
            {
                pq.push(make_pair(visited[i][l] - 1, make_pair(idx, _idx)));
            }
        }
    }

    for (ll i = 0; i < nodes.size(); ++i)
    {
        parents[i] = i;
    }

    ll result = 0;
    while (!pq.empty())
    {
        ll w = pq.top().first, from = pq.top().second.first, to = pq.top().second.second;
        pq.pop();
        if (find(from) != find(to))
        {
            merge(from, to);
            result += w;
        }
    }

    ll root = find(0);
    for (ll i = 0; i < nodes.size(); ++i)
    {
        if (find(i) != root)
        {
            result = -1;
            goto END;
        }
    }

END:
    cout << result << "\n";

    return 0;
}