[ 백준 17142 ] 연구소3 (C++)

백준의 연구소3(17142) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 연구소2와 굉장히 비슷한데 한 가지만 딱 조심해주면 되는 문제이다.

   연구소2를 아직 풀지 않았다면, 먼저 풀어보고 오는 것이 좋을 것 같다고 생각된다..

   [ 연구소2 문제 바로가기(Click) ]

   [ 연구소2 풀이 바로가기(Click) ]

  

   ( 문제가 연구소2와 굉장히 비슷한 관계로 비교하면서 풀이를 진행하겠습니다. )

   연구소2 에서는 선택하지 않은 바이러스들에 대해서는 빈 공간인 0과 똑같은 취급을 해버리면 되었었다.

   하지만, 이 문제에서는 그렇지 않다. 다음과 같은 예를 보면서 생각해보자.

  

   위와 같은 맵이 있다고 생각해보자. 저 4개의 바이러스 중에서 선택할 수 있는 바이러스는 1개라고 가정하겠다.

   이 때, (0, 0)에 존재하는 '2'를 선택했다고 생각해보면 연구소2에서는 다음과 같이 생각하면 문제를 해결할 수 있었다.

  

   이와 같이 생각하고 바이러스를 퍼뜨려보면, 총 2초가 걸린다는 것을 알 수 있다. 실제로 답이 '2'가 맞다.

   하지만 연구소3인 이 문제에서는 다르다.

  

   연구소3에서는 위의 그림과 같이 생각을 해야 한다. 즉, 선택되지 않은 바이러스가 빈 공간인 0의 역할을 하는 것이

   아니라, 또 다른 활성화 되어 있지 않은 비활성화 바이러스 상태로 존재한다는 조건이 있기 때문에 저렇게 표시를

   해볼 수 있다. 그렇다면 정답은 몇초일까? 정답은 0 초이다. 왜냐하면, 활성화된 바이러스가 비활성화된 바이러스가

   있는 곳으로 가서 활성화 시키는 것은, 바이러스가 퍼뜨린 시간으로 계산하지 않는다.

   사실 본인도 이 부분이 이해도 잘 안갔고 그러다보니 구현이 제대로 되지 않아 계속해서 틀렸었는데, 본인이 이해한

   바로는 이 설명이 맞는 것 같다.

   즉, 빈 공간인 0인 지점에 방문을 할 때에는 바이러스가 퍼뜨린 시간에 영향을 주지만, 비활성화된 바이러스가 있는

   곳으로 바이러스가 퍼지는 것은 바이러스가 퍼뜨린 시간에 영향을 미치지 않는 다는 것이다.

   아직도 이 말이 이해가 잘 되지 않는다면, 예제입력7 의 입력과 출력을 보면 알 수 있을 것이다.

2) 그렇다면 본격적인 구현에 들어가보도록 하자. 바이러스를 선택하고 하는 그런 과정은 연구소2와 동일하게 조합을

   이용해서 선택해준다. ( 무슨 말인지 모르시겠으면 연구소2 풀이 읽어보고 오기 ! )

   바이러스를 퍼뜨리는 부분을 구현한 BFS탐색 하는 부분에 대해서만 간단하게 설명하겠다.

   먼저 본인은 맵의 상태를 받는 2차원 배열 이외에, 시간을 저장하는 2차원 배열을 하나 더 만들어 주었다.

   또한, 초기에 입력을 받을 때 빈 공간의 갯수를 Count해주었다.

   탐색을 진행하면서, 빈 공간을 탐색할 때 마다 그 갯수를 Count해줄 것이고, 이 갯수와 처음에 Count해놓은 빈 공간의

   갯수와 비교해서 모두 탐색이 가능한지 확인해 주었다.

  

   위에서 반복해서 말한 것이지만, 2와 0을 구분해서 탐색해 주어야 한다. 2를 탐색할 때에는 전체시간에 영향을

   미치지 않는다. 이를 체크해주기 위해서 본인은 (본문 : int Total_Time) 이라는 변수를 하나 만들어서 관리해 주었다.

   0을 방문할 때에는 그 시간을 계속해서 갱신해 주었지만, 비활성화된 바이러스를 방문할 때에는 그 시간을 갱신해주지

   않았다.

   이 부분만 조심한다면 연구소2와 비슷하게 해결할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M, Empty_Place, Answer = 987654321;
int MAP[MAX][MAX];
int Time[MAX][MAX];
bool Select[10];
 
vector<pair<int, int>> 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] == 0) Empty_Place++;
            else if (MAP[i][j] == 2) Virus.push_back(make_pair(i, j));
        }
    }
}
 
void Spread_Virus(queue<pair<int, int>> Q)
{
    int Infect_Place = 0;
    int Total_Time = 0;
    while (Q.empty() == 0)
    {
        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 (MAP[nx][ny] != 1 && Time[nx][ny] == -1)
                {
                    Time[nx][ny] = Time[x][y] + 1;
                    if (MAP[nx][ny] == 0)
                    {
                        Infect_Place++;
                        Total_Time = Time[nx][ny];
                    }
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
    if (Infect_Place == Empty_Place)
    {
        Answer = Min(Answer, Total_Time);
    }
}
 
void Select_Virus(int Idx, int Cnt)
{
    if (Cnt == M)
    {
        queue<pair<int, int>> Q;
        memset(Time, -1, sizeof(Time));
        for (int i = 0; i < Virus.size(); i++)
        {
            if (Select[i] == true)
            {
                Q.push(make_pair(Virus[i].first, Virus[i].second));
                Time[Virus[i].first][Virus[i].second] = 0;
            }
        }
        
        Spread_Virus(Q);
        return;
    }
 
    for (int i = Idx; i < Virus.size(); i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Select_Virus(i + 1, Cnt + 1);
        Select[i] = false;
    }
}
 
void Solution()
{
    Select_Virus(0, 0);
    if (Answer == 987654321) cout << -1 << endl;
    else 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;
}