[Algorithm/C++17] 백준 17142 연구소 3

문제

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

17142번: 연구소 3

풀이 방법

백준 17141 연구소 2와 비슷한 문제다. (풀이)

차이점은  활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다는 것이다.

따라서 탐색할 때 비활성 바이러스를 만나면 퍼뜨린 시간을 계산하지 않아도 된다는 것만 주의하면 된다.

 

코드 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    vector<vector<int>> v(N, vector<int>(N));
    vector<pair<int,int>> virus;
    vector<int> combi;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            scanf("%d", &v[i][j]);
            if(v[i][j] == 2)
            {
                virus.push_back({i,j});
            }
        }
    }
    // 조합 
    for(int i=0; i<M; i++)
    {
        combi.push_back(1);
    }
    for(int i=combi.size(); i<virus.size(); i++)
    {
        combi.push_back(0);
    }
    
    // prev_permutation을 이용해 전체 바이러스 중 M개를 선택한다.
    int answer = 0x7fffffff;
    do
    {
        queue<pair<int, int>> q;
        vector<vector<int>> visited(N, vector<int>(N, -1));
        // 바이러스를 놓는다.
        for(int i=0; i<virus.size(); i++)
        {
            if(combi[i] == 1)
            {
                q.push({virus[i].first, virus[i].second});
                visited[virus[i].first][virus[i].second] = 0;
            }
        }
        
        // 바이러스를 퍼뜨린다.
        int count = 1;
        while(!q.empty())
        {
            int qsize = q.size();
            for(int i=0; i<qsize; i++)
            {
                int y = q.front().first;
                int x = q.front().second;
                q.pop();
                for(int j=0; j<4; j++)
                {
                    int ny = y + dy[j];
                    int nx = x + dx[j];
                    
                    if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
                    if(visited[ny][nx] != -1 || v[ny][nx] == 1) continue;
                
                	q.push({ny,nx});
                    // 탐색할 때 비활성 바이러스를 만나면 퍼뜨린 시간을 계산하지 않아도 된다.
                	if(v[ny][nx] == 2)
                		visited[ny][nx] = visited[y][x];
                	else
                		visited[ny][nx] = count;
                }
            }
            count++;
        }
        
        // 바이러스가 다 퍼졌는지 확인한다.
        bool success = true;
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                if(v[i][j] == 0 && visited[i][j] == -1) 
                {
                    success = false;
                    break;
                }
            }
            if(!success) break;
        }
        // 다 퍼졌으면 퍼뜨린 시간을 구한다.
        int time = -1;
        if(success) 
        {
        	for(int i=0; i<N; i++)
        	{
        		for(int j=0; j<N; j++)
        		{
        			time = max(time, visited[i][j]);
        		}
        	}
        }
        
        if(time != -1)
        	answer = min(answer, time);
        
    }while(prev_permutation(combi.begin(), combi.end()));
    
    // 정답 출력
    if(answer == 0x7fffffff)
    	printf("-1\n");
    else
    	printf("%d\n", answer);
    
    return 0;
}

고찰

90%대에서 계속 틀리다가 반례 모음집을 찾아서 해결했다.