[Algorithm/C++17] 백준 17141 연구소 2

문제

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

17141번: 연구소 2

풀이 방법

주어진 연구소 정사각형의 '2'의 위치에 바이러스를 M개 놓아본 후, 그것을 퍼뜨렸을 때 모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제다.

 

바이러스를 퍼뜨리는 것이나 최소 시간을 구하는 건 다른 문제에서도 많이 해봤기 때문에 어려움은 없을 것이다. (만약에 어렵다면 미로 탐색이나 불 등 다른 문제를 더 풀어보자.) 하지만 전체 바이러스 개수 중 M개를 선택해 놓는 것이 좀 어렵다. 이는 C++의 prev_permutation이나 next_permutation을 이용하면 쉽게 풀 수 있다.

 

예를 들어 M = 3 이고 전체 바이러스 개수가 5라고 하면, 우선 1 1 1 0 0배열을 만든다. 그리고 permuation함수로 그것의 순열인 1 0 1 1 0, 1 0 0 1 1 등을 만들어내어 어떤 위치에 바이러스를 놓을지 선택한다. 그 뒤에는 문제에 나와있는대로 시뮬레이션해주면 된다. 아래 코드를 참고하면서 읽어보는 게 더 이해에 도움이 될 것이다.

 

그리고 이렇게 시도하면서 성공한 경우에만 최소 시간을 구해야 하고 모든 경우가 실패했을 경우 -1을 출력해야 한다.  이는 정답 벡터에 모든 시도의 결과값을 추가하고 모든 경우가 -1이면 -1을 출력, 아니면 최소값을 출력하는 식으로 구현했다.

 

코드

#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개를 선택한다.
    vector<int> answer;
    do
    {
        queue<pair<int, int>> q;
        vector<vector<bool>> visited(N, vector<bool>(N, false));
        // 바이러스를 놓는다.
        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] = true;
            }
        }
        
        // 바이러스를 퍼뜨린다.
        int result = 0;
        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] || v[ny][nx] == 1) continue;
                    
                    q.push({ny,nx});
                    visited[ny][nx] = true;
                }
            }
            result++;
        }
        // 바이러스가 다 퍼졌는지 확인한다.
        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]) 
                {
                    success = false;
                    break;
                }
            }
            if(!success) break;
        }
        // 다 퍼졌으면 정답 리스트에 시간 추가, 안퍼졌으면 -1추가
        if(success) answer.push_back(result-1);
        else answer.push_back(-1);
    }while(prev_permutation(combi.begin(), combi.end()));
    
    // 정답 리스트 중 성공했을 때 가장 최소 시간을 구해 출력한다.
    // 성공한 경우가 없으면 -1을 출력한다.
    int min_answer = 0x7fffffff;
    for(int i=0; i<answer.size(); i++)
    {
    	if(answer[i] != -1)
    		min_answer = min(min_answer, answer[i]);
    }
    if(min_answer != 0x7fffffff) printf("%d", min_answer);
    else printf("-1");
    
    return 0;
}

고찰

조합을 구하는 것이나 정답을 출력하는 것 빼곤 어렵지 않았던 문제.