링크
https://www.acmicpc.net/problem/1944
문제
세준이는 어느 날 획기적인 로봇을 한 개 개발하였다. 그 로봇은 복제 장치를 이용하면 자기 자신을 똑같은 로봇으로 원하는 개수만큼 복제시킬 수 있다. 세준이는 어느 날 이 로봇을 테스트하기 위하여 어떤 미로에 이 로봇을 풀어 놓았다. 이 로봇의 임무는 미로에 흩어진 열쇠들을 모두 찾는 것이다. 그리고 열쇠가 있는 곳들과 로봇이 출발하는 위치에 로봇이 복제할 수 있는 장치를 장착해 두었다.
N*N의 정사각형 미로와 M개의 흩어진 열쇠의 위치, 그리고 이 로봇의 시작 위치가 주어져 있을 때, 모든 열쇠를 찾으면서 로봇이 움직이는 횟수의 합을 최소로 하는 프로그램을 작성하여라. 로봇은 상하좌우 네 방향으로 움직이며, 로봇이 열쇠가 있는 위치에 도달했을 때 열쇠를 찾은 것으로 한다. (복제된 로봇이어도 상관없다) 하나의 칸에 동시에 여러 개의 로봇이 위치할 수 있으며, 로봇이 한 번 지나간 자리라도 다른 로봇 또는 자기 자신이 다시 지나갈 수 있다. 복제에는 시간이 들지 않으며, 로봇이 움직이는 횟수의 합은 분열된 로봇 각각이 움직인 횟수의 총 합을 말한다. 복제된 로봇이 열쇠를 모두 찾은 후 같은 위치로 모일 필요는 없다.
입력
첫째 줄에 미로의 크기 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을 출력하면 된다.
예제 입력 및 출력
풀이 코드(C++)
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;
using tiii = tuple<int,int,int>;
int n,m,temp = 1,board[51][51],dist[51][51];
vector<pii> nodes;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int OOB(int nx,int ny) { return (nx < 0 || nx >= n || ny < 0 || ny >= n);}
struct UnionFind {
vector<int> parent, rank, cnt;
UnionFind(int n) : parent(n), rank(n, 1), cnt(n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int Find(int x) {
return x == parent[x] ? x : parent[x] = Find(parent[x]);
}
bool Union(int a, int b) {
a = Find(a), b = Find(b);
if (a == b) return 0;
if (rank[a] < rank[b]) swap(a, b);
parent[b] = a;
rank[a] += rank[a] == rank[b];
cnt[a] += cnt[b];
return 1;
}
};
int main() {
fastio;
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
char c; cin >> c;
if(c == '1') board[i][j] = -1;
else if(c == '0') board[i][j] = 0;
else if(c == 'S' || c == 'K'){
board[i][j] = temp++;
nodes.pb({i ,j});
}
}
}
vector<tiii> e;
// BFS
for(auto [x, y] : nodes){
for(int i = 0; i < n; i++) fill(dist[i],dist[i] + n, -1);
queue<pii> q;
dist[x][y] = 0;
q.push({x, y});
while(!q.empty()){
auto cur = q.front(); q.pop();
for(int i = 0; i < 4; i++){
auto nx = cur.X + dx[i];
auto ny = cur.Y + dy[i];
if(OOB(nx,ny) || board[nx][ny] == -1 || dist[nx][ny] != -1) continue;
q.push({nx, ny});
dist[nx][ny] = dist[cur.X][cur.Y] + 1;
if(board[nx][ny] == 0) continue; // nx,ny가 S 나 K일때만 e에 넣음.
e.pb({dist[nx][ny], board[x][y], board[nx][ny]});
}
}
}
// MST
sort(e.begin(), e.end());
UnionFind UF(m + 2);
int sum = 0,cnt = 0;
for(auto [c, a, b] : e){
a = UF.Find(a),b = UF.Find(b);
if(a == b) continue;
UF.Union(a,b);
sum += c;
cnt++;
if(cnt == m) break;
}
cout << (cnt==m ? sum : -1) << "\n";
return 0;
}