17142. 연구소 3

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

 

 

Point

1. 연구소 2와 달리 비활성화 바이러스가 존재.

2. 활성화 바이러스가 비활성화 바이러스가 있는 칸으로 가면 비활성화 바이러스가 활성화 바이러스로 바뀐다.

3. 활성화 바이러스를 선택하는 경우의 수는 최대 10개중에서 5개 고르는 경우로 10C5 = 252가지 경우가 존재한다.

4. 최대 10C5에 대해 BFS를 실행하면 O(252*50*50)=630,000 으로 시간 안에 통과 가능.

이 테스트케이스의 경우 선택할 수 있는 2의 경우의 수는 총 4개중에 2개이다. 따라서 총 4C2 = 6가지 경우의 수가 존재한다.

 

case 2

위 케이스의 경우 두 가지 경우가 존재하는데 두 번째 경우를 보면 답이 3이라고 기대할 수 있는데, 답은 2이다.

3이 들어간 칸은 비활성화 바이러스가 있는 칸으로  최대 시간을 계산할 때에는 비활성화 바이러스칸을 살펴보지 않아도 된다.

Why ? 문제에서 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구하라고 했기 때문에 비활성화 바이러스 칸은 살펴보지 않아도 된다.

 

한 가지 케이스를 더 살펴보자.

 

case 3

이 케이스의 경우도 두 가지 경우가 존재한다

비활성화 바이러스에 활성화 바이러스가 닿고 난 뒤에는 어떻게 진행을 해주어야 할까?

연구소 2 문제와 마찬가지로 BFS를 진행할 때에는 비활성화 바이러스가 있는 칸을 빈 칸으로 취급해주고, 

최소 시간을 계산할 때에는 비활성화 바이러스가 있는 칸을 살펴보지 않으면 된다. 

 

연구소 2 문제와의 차이점은 단지 비활성화 바이러스가 있는 칸을 살펴보는지에 대한 여부.

 

---

소스 코드를 살펴보자.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 
using namespace std;
vector<vector<int>> area(51,vector<int>(51));
vector<pair<int,int>> virus;
int n, m;
int ans=-1;
int dy[]={-1,1,0,0};
int dx[]={0,0,1,-1};
int blank;

int bfs(queue<pair<int,int>> &q,vector<vector<bool>> check, vector<vector<int>> visited, vector<vector<bool>> &awake,int ans)
{   
    int result=-1;
    int cnt = 0;
    while(!q.empty())
    {   
        if(blank==cnt) 
        {
            break;
        }

        for(int i=0;i<q.size();i++)
        {
            int y = q.front().first;
            int x = q.front().second;
 
            for(int i=0;i<4;i++)
            {
                int ny = y+dy[i];
                int nx = x+dx[i];

                if(ny>=0 && nx>=0 && ny<n && nx<n)
                {
                    if(check[ny][nx]==false && area[ny][nx]!=1)
                    {   
                        if(area[ny][nx]==2 && awake[ny][nx]==false)
                        {
                            awake[ny][nx]=true;
                        }

                        if(area[ny][nx]==0) cnt++;

                        visited[ny][nx] = visited[y][x]+1;
                        check[ny][nx]=true;
                        q.push({ny,nx});
                    }
                }
            }
            
            q.pop();
        }    
    }


    if(blank==cnt)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {   
                if(awake[i][j]==false)
                    result = max(result,visited[i][j]);
                if(area[i][j]==0 && check[i][j]==false)
                    return -1;
            }
        }
    }

    return result;
}

int main()
{
    FASTio;
    cin >> n >> m;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)  
        {
            cin >> area[i][j];
            if(area[i][j]==2)
            {   
                virus.push_back({i,j});
            }
            else if(area[i][j]==0)
            {
                blank++;
            }

        }
    }

    // 조합 초기 작업
    vector<int> k(virus.size());
    for(int i=0;i<m;i++)
    {
        k[i] = 1;
    }

    for(int i=m;i<virus.size();i++)
    {
        k[i] = 0;
    }
    sort(k.begin(),k.end());

    // 조합 
    do
    {   
        queue<pair<int,int>> q;
        vector<vector<int>> visited(51,vector<int>(51,0));
        vector<vector<bool>> check(51,vector<bool>(51,false));
        vector<vector<bool>> awake(51,vector<bool>(51,false));
        
        for(int i=0;i<virus.size();i++)
        {
            if(k[i]==1)
            {   
                int y,x;
                tie(y,x) = virus[i];
                q.push(make_pair(y,x));
                check[y][x]=true;
                awake[y][x]=true;
            }
        }

        int a = bfs(q,check,visited,awake,ans);
        if(a==-1) continue;
        else
        {
            if(ans==-1 || ans>a)
            {
                ans = a;
            }
        }

    } while (next_permutation(k.begin(),k.end()));
    
    cout << ans;

    return 0;
}

 

Main

1. 배열 입력 -> 2일 경우 조합 선택지에 포함시키기 위해 벡터 푸쉬, 0일 경우 빈칸의 개수++

2. next_permutation을 이용한 조합을 이용하기 위한 초기작업

3. 2의 총 개수 중에 m개 선택하는 각 경우에 대한 BFS

 

BFS

1. 현재 큐에는 활성화 된 바이러스 m개가 들어있는 상황

2. 연구소 2와 마찬가지로 큐를 한번 돌면서 BFS를 진행한다.

3. BFS를 진행하는 도중 main함수에서 빈칸의 개수만큼 다 채운 경우 더 살펴볼 필요가 없으므로 BFS를 종료한다.

4. BFS를 진행하는 도중 비활성화 바이러스를 만나는 경우 활성화 시켜준다.

5. 그 외는 연구소 2와 동일한데 BFS가 종료되고 바이러스가 퍼지는데 걸린 시간을 살펴볼 때에 비활성화 바이러스 칸은 살펴보지 않는다.

 

 

 

 분명 시간복잡도를 계산했을 때 통과될 것이라 생각했는데 알고보니 내부의 로직에 문제가 있었다.

 

AC 코드 (BFS)

    while(!q.empty())
    {   
        if(blank==cnt) 
        {
            break;
        }

        for(int i=0;i<q.size();i++)
        {
            int y = q.front().first;
            int x = q.front().second;
 
            for(int i=0;i<4;i++)
            {
                int ny = y+dy[i];
                int nx = x+dx[i];

                if(ny>=0 && nx>=0 && ny<n && nx<n)
                {
                    if(check[ny][nx]==false && area[ny][nx]!=1)
                    {   
                        if(area[ny][nx]==2 && awake[ny][nx]==false)
                        {
                            awake[ny][nx]=true;
                        }

                        if(area[ny][nx]==0) cnt++;

                        visited[ny][nx] = visited[y][x]+1;
                        check[ny][nx]=true;
                        q.push({ny,nx});
                    }
                }
            }
            
            q.pop();
        }    
    }

 

시간초과 코드 (BFS)

    while(!q.empty())
    {   
        if(blank==cnt) 
        {
            break;
        }

        for(int i=0;i<q.size();i++)
        {
            int y = q.front().first;
            int x = q.front().second;
 
            for(int i=0;i<4;i++)
            {
                int ny = y+dy[i];
                int nx = x+dx[i];

                if(ny>=0 && nx>=0 && ny<n && nx<n)
                {
                    if(check[ny][nx]==false && area[ny][nx]!=1)
                    {   
                        if(area[ny][nx]==2 && awake[ny][nx]==false)
                        {
                            awake[ny][nx]=true;
                        }

                        if(area[ny][nx]==0) cnt++;

                        visited[ny][nx] = visited[y][x]+1;
                        check[ny][nx]=true;
                        q.push({ny,nx});
                    }
                }
            }     
        }    
        q.pop();
    }

 

q를 pop하는 시점이 상하좌우를 살피고 푸쉬를 한 직후 바로 팝을 해주어야 하는데 q size만큼 for문을 돌린뒤에 뒤늦게 팝을 해주어서 시간초과가 발생했다. 이렇게 사소해보이지만 중요한 로직은 디버깅하기 어려우니 구현할때에 더욱 신경써야겠다.