백준) 1944 복제 로봇

1944. 복제 로봇 

문제

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

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

입력

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

출력

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

예제 입력 

5 2
11111
1S001
10001
1K1K1
11111

예제 출력 

6

1. 접근

S에서 시작해서 K로 가야한다. K에 도착하면 원하는 수만큼 자신을 복사할 수 있으며, 최종적으로 모든 K에 도착해야한다.

이 때 가장 적은 경로의 합을 구하는 문제다.

S와 K들 사이의 경로를 그래프처럼 그려보자.

예시 입력에는 2개의 K개 있으며 (K1, K2) S에서 K1으로 가는 비용은 2, K2는 4이다.

먼저 K1으로 가기로 해보고, 도착 한뒤 자아 분열을 통해 K2로 가는 비용은 4이다.

따라서 우리는 S와 K들 사이의 최소거리를 비용으로 하는 간선들로 이루어진 그래프로 문제를 이해할 수 있다.

그러면 문제에서 원하는 해답은 그래프의 어떤 모습이겠는가?

그래프를 최소신장트리화시켜 비용의 합을 원하는 문제임을 알 수 있다.

2. 풀이

최소거리를 먼저 구해서 간선화시키는 방법이 필요할 것이다. 이에 BFS를 차용한다.

매 S, K들 마다 BFS를 돌려서 간선들을 만들고 저장한다.

BFS시에 모든 K를 방문하지 못한다면 길이 없는 것이므로 -1을 출력한다.

그 후엔 디스조인트-셋을 활용한 크루스칼 알고리즘을 사용하면 된다.

키의 번호는 정해져 있지 않으므로, 각 좌표의 키 번호를 지정하고 저장할 배열이 필요할 것이다.

이후 저장된 간선들에 대해 정렬하고 크루스칼 알고리즘을 돌리자.

참고 : http://js1jj2sk3.tistory.com/22

3. 코드

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
struct cd {
    int x, y;
};
cd start;
vector<cd> key_list;
 
struct edge {
    int weight, from, to;
};
bool cmp(const edge& e1, const edge& e2) {
    return e1.weight < e2.weight;
}
vector<edge> E;
 
int n, m, i, j, cx, cy, nx, ny, cnt, sum;
int key_cnt, key_num[51][51];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int dist[51][51];
bool visit[51][51];
char map[51][51];
 
int parent[251];
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    parent[x] = y;
}
 
int bfs(int x, int y, int mom) {
    memset(visit, 0, sizeof(visit));
    memset(dist, 0, sizeof(dist));
    key_cnt = 1;
 
    queue<cd> q;
    q.push({ x,y });
    visit[x][y] = true;
 
    while (!q.empty()) {
        cx = q.front().x;
        cy = q.front().y;
        q.pop();
 
        for (i = 0; i < 4; ++i) {
            nx = cx + dir[i][0];
            ny = cy + dir[i][1];
 
            if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                continue;
            if (visit[nx][ny] || map[nx][ny] == '1')
                continue;
 
            dist[nx][ny] = dist[cx][cy] + 1;
            visit[nx][ny] = true;
 
            if (map[nx][ny] == 'K') {
                key_cnt++;
                E.push_back({ dist[nx][ny], mom, key_num[nx][ny] });
            }
 
            if (key_cnt == key_list.size())
                return key_cnt;
 
            q.push({ nx,ny });
        }
    }
    return key_cnt;
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; ++i) {
        scanf("%s", map[i]);
        for (j = 0; j < n; ++j) {
            if (map[i][j] == 'S') {
                start = { i,j };
                map[i][j] = 'K';
            }
            if (map[i][j] == 'K') {
                key_list.push_back({ i,j });
                key_num[i][j] = ++key_cnt;
            }
        }
    }
 
    for (auto key : key_list) {
        if (bfs(key.x, key.y, key_num[key.x][key.y]) != key_list.size()) {
            puts("-1");
            return 0;
        }
    }
 
    sort(E.begin(), E.end(), cmp);
 
    for (i = 0; i <= key_list.size(); ++i)
        parent[i] = i;
 
    i = 0;
    while (cnt != key_list.size() - 1) {
        cx = find(E[i].from);
        cy = find(E[i].to);
 
        if (cx != cy) {
            unite(cx, cy);
            sum += E[i].weight;
            cnt++;
        }
        i++;
    }
    printf("%d", sum);
    return 0;
}