[ 백준 17141 ] 연구소2 (C++)

백준의 연구소2(17141) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 주어지는 맵에서 M개의 좌표를 선택하여, 바이러스를 설치하고 바이러스가 모든 맵에 퍼지는데 걸리는 최소시간을 구해야

    하는 문제이다. 본인은 이 문제를 전체에서 뽑을 수 있는 M개의 경우의 수를 모두 뽑아서 답을 모두 구해보고 최소시간을

    구하는 완전탐색 방식으로 구현해 보았다. 그렇다면 어떻게 M개를 뽑을지 한번 알아보자.

    먼저 맵에서 '2'가 5개가 존재한다고 생각해보자. 즉, 바이러스를 설치할 수 있는 곳이 총 5개가 존재하는 경우이다.

    이 때, M = 3이라고 가정해보면 우리는 '5개 중에 3개를 뽑는 수열'을 구현해야 한다.

    과연 순열일까 조합일까?? 바로 조합이다. 왜 순열이 아닌지, 왜 조합인지 알아보도록 하자.

    쉽게 설명하기 위해서 2차원 좌표가 아닌 1차원 점으로 설명해 보겠다.

    예를 들어서 (0, 1, 2, 3, 4) 이렇게 총 5개의 점에서 3개의 점을 뽑는다고 생각해보자.

    그렇다면, (0, 1, 2) 점을 뽑고 바이러스를 퍼뜨리는 것과, (2, 0, 1) 점을 뽑고 바이러스를 퍼드릴 떄 걸리는 시간이 다를까?

    아니다. 아마 결과가 똑같을 것이다. 즉, 어떻게 뽑든 순서에는 상관이 없으므로 '조합'을 구현하면 된다.

    아직 조합을 구현하는 법을 잘 모른다면 아래의 글을 읽고 오도록 하자.

    [ 조합 구현하는법 알아보기(Click) ]

2) 사실 위의 조합만 구현한다면 문제에서 핵심되는 부분은 끝났다고 봐도 무방하다. 별다른 특별한 조건이 없으므로

    선택한 바이러스들을 계속해서 퍼트려 주기만 하면 된다. 본인은 이 부분은 BFS 탐색법을 통해서 하나하나 넓혀가면서

    탐색을 해 주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M, Answer = 987654321;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool Select[10];
vector<pair<int, int>> V;
vector<pair<int, int>> Select_Virus;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    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] == 2) V.push_back(make_pair(i, j));
        }
    }
}
 
bool Check()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] == 1) continue;
            if (Visit[i][j] == false) return false;
        }
    }
    return true;
}
 
void Spread_Virus()
{
    queue<pair<int, int>> Q;
    for (int i = 0; i < Select_Virus.size(); i++)
    {
        int x = Select_Virus[i].first;
        int y = Select_Virus[i].second;
        Q.push(make_pair(x, y));
        Visit[x][y] = true;
    }
 
    int Cnt = 0;
    while (Q.empty() == 0)
    {
        int S = Q.size();
        for (int Qs = 0; Qs < S; Qs++)
        {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();
 
            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 (Visit[nx][ny] == false && MAP[nx][ny] != 1)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(nx, ny));
                    }
                    
                }
            }
        }
        if(Q.size() !=0) Cnt++;
    }
    if(Check() == true) Answer = Min(Answer, Cnt);
}
 
void Select_Virus_Pos(int Idx, int Cnt)
{
    if (Cnt == M)
    {
        memset(Visit, false, sizeof(Visit));
        Spread_Virus();
        return;
    }
 
    for (int i = Idx; i < V.size(); i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Select_Virus.push_back(V[i]);
        Select_Virus_Pos(i, Cnt + 1);
        Select_Virus.pop_back();
        Select[i] = false;
    }
}
 
void Solution()
{
    Select_Virus_Pos(0, 0);
    if (Answer == 987654321) Answer = -1;
    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;
}