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

백준의 복제로봇(1944) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 시작점에서 모든 열쇠를 주울 때, 로봇이 움직인 횟수를 구해야 하는 문제이다.

로봇은 복제해서 여러개의 로봇을 움직이게 할 수 있고, 로봇이 여러개일 때는 모든 로봇의 움직인 횟수를 모두 더해서

최소 값을 구해야 한다.

처음에 어떻게 접근해야 할지 잘 모르겠었는데, 생각해보다가 이 문제는 MST(최소 스패닝 트리)로 구현할 수 있을 거라

생각했다. 먼저, 어떤 점에서 최소 스패닝트리와 연관성이 있는지 알아보자.

아래와 같은 맵을 한번 생각해보자.

위의 예시 같은 경우 눈으로 문제를 푼다고 생각해보면, 시작점 'S'에서 빨강색 'K'로 가는데 움직이는 횟수 3번,

시작점에서 로봇을 복제해서 파랑색 'K'로 가는데 움직이는 횟수 3번, 총 2개의 로봇이 각각 3번씩 움직이면

6번 만에 2개의 열쇠를 모두 주울 수 있게 된다.

그럼 위의 루트가 아닌 경우를 생각해보자.

로봇1이 S → 빨강색 'K' → 파랑색 'K' 로 가게 되면 9번 움직이게 된다. (S → 빨강색K : 3번 , 빨강색K → 파랑색K : 6번)

반대로 S → 파랑색 'K' → 빨강색 'K' 로 가게 되도 마찬가지이다.

그럼 위의 시작점과 열쇠들을 아래와 같은 그래프의 형태로 생각해볼 수 있다.

이런 형태의 그래프인데, 위의 그래프에서 최소 스패닝 트리의 형태는 어떻게 될까 ??

아래와 같은 형태일 것이다.

최소스패닝 트리가 위의 형태일 것이고, 최소스패닝트리를 만들기 위해서 필요한 비용은 '6'이 될 것이다.

문제에서 주어진 'S'과 'K'간의 관계를 위와 같은 그래프의 형태로 생각해보면, MST를 구하는 문제라는 것을 알 수 있다.

하지만 ! 이 문제는 간선의 가중치가 주어지지 않는다. 2차원맵만 주어지고, 그 이외의 가중치를 알려주지 않는다.

따라서, 가중치를 직접 구해야 하는 과정이 필요하다.

본인은 이 과정을 '너비우선탐색(BFS)' 을 통해서 구해주었다.

먼저, 시작점 'S'와 모든 'K'에 대해서 BFS 탐색을 통해서 'S'와 'K'들의 거리를 모두 구해주었고, 그 이후에

'K'끼리 서로서로 간의 거리를 모두 구해주었다.

이 후, MST를 구현하는 알고리즘 중, 크루스칼 알고리즘을 이용해서 그 비용을 구해주었다.

MST 혹은 크루스칼 알고리즘에 대해서 잘 모른다면 아래의 글을 읽고 읽고오도록 하자.

[ 크루스칼 알고리즘 알아보기 (Click) ]

[ 프림 알고리즘 알아보기 (Click) ]

[ 프림 알고리즘 알아보기(2) (Click) ]

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
 
#define endl "\n"
#define MAX 50
#define KEY_MAX 255
using namespace std;
 
int N, M, Key_Num, Answer;
int Key_Number[MAX][MAX];
int Parent[KEY_MAX];
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool Flag = true;
pair<int, int>Start;
vector<pair<int, int>> Key;
vector<pair<int, pair<int, int>>> Edge;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    Key_Num = 1;
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'S')
            {
                Start.first = i;
                Start.second = j;
            }
            else if (MAP[i][j] == 'K')
            {
                Key.push_back(make_pair(i, j));
                Key_Number[i][j] = Key_Num++;
            }
        }
    }
}
 
void BFS(int Sx, int Sy, int Ex, int Ey, int Node1, int Node2)
{
    memset(Visit, false, sizeof(Visit));
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(Sx, Sy), 0));
    Visit[Sx][Sy] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (x == Ex && y == Ey)
        {
            Edge.push_back(make_pair(Cnt, make_pair(Node1, Node2)));
            return;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny] == '1') continue;
                if (Visit[nx][ny] == true) continue;
 
                Visit[nx][ny] = true;
                Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
            }
        }
    }
    Flag = false;
}
 
void Calculate_Distance()
{
    for (int i = 0; i < Key.size(); i++)
    {
        int x = Key[i].first;
        int y = Key[i].second;
        BFS(Start.first, Start.second, Key[i].first, Key[i].second, 0, Key_Number[x][y]);
 
        if (Flag == false)
        {
            cout << -1 << endl;
            return;
        }
    }
    for (int i = 0; i < Key.size(); i++)
    {
        int x = Key[i].first;
        int y = Key[i].second;
 
        for (int j = i + 1; j < Key.size(); j++)
        {
            int xx = Key[j].first;
            int yy = Key[j].second;
 
            BFS(x, y, xx, yy, Key_Number[x][y], Key_Number[xx][yy]);
            if (Flag == false)
            {
                cout << -1 << endl;
                return;
            }
        }
    }
}
 
int Find_Parent(int A)
{
    if (A == Parent[A]) return A;
    else return Parent[A] = Find_Parent(Parent[A]);
}
 
bool Same_Parent(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
 
    if (A == B) return true;
    return false;
}
 
void Union(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
 
    Parent[B] = A;
}
 
void Kruskal()
{
    for (int i = 0; i < Key_Num; i++) Parent[i] = i;
    sort(Edge.begin(), Edge.end());
 
    for (int i = 0; i < Edge.size(); i++)
    {
        int Cost = Edge[i].first;
        int Node1 = Edge[i].second.first;
        int Node2 = Edge[i].second.second;
 
        if (Same_Parent(Node1, Node2) == false)
        {
            Union(Node1, Node2);
            Answer = Answer + Cost;
        }
    }
}
 
void Solution()
{
    Calculate_Distance();
    if (Flag == false) return;
 
    Kruskal();
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}