[백준 17142번] 연구소 3

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

17142번: 연구소 3

풀이) 

1. 바이러스 시작점을 dfs를 통해 조합을 구성한다.

2. 이후 퍼트리는 지역이 0거나 2이면서 게임이 끝나지 않은 상황이면 이면 다음 값들을 큐에 넣고 bfs를 진행한다.

3. 끝난시점에서 전부 퍼트려진 상태가 됐을 때 중에서 가장 적은 시간을 출력한다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector <pair<int, int> > virus;
int map[51][51], map_c[51][51];
int N, M, ans = 2e9, test = 0;
int dir_x[4] = {-1, 1, 0, 0};
int dir_y[4] = {0, 0, 1, -1};
int selected[11];

void copy()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            map[i][j] = map_c[i][j];
}

int endCheck()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (map[i][j] == 0)
                return (0);
    return (1);
}

void spreadVirus()
{
    int total = 0;
    queue <pair<pair<int, int>, int> > q;
    for (int i = 0; i < virus.size(); i++)
    {
        if (selected[i])
        {
            q.push(make_pair(make_pair(virus.at(i).first, virus.at(i).second), 1));
            map[virus[i].first][virus[i].second] = 3;
        }
    }
    while (!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int second = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dir_x[i];
            int ny = y + dir_y[i];
            if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1)
                continue ;
            if (map[nx][ny] == 0 || (map[nx][ny] == 2 && !endCheck()))
            {
                map[nx][ny] = second;
                q.push(make_pair(make_pair(nx, ny), second + 1));
                total = second > total ? second : total;
            }
        }
    }
    if (endCheck())
        ans = total < ans ? total : ans;
}

void permutation(int size, int cnt)
{
    test++;
    if (size > virus.size() - 1)
        return ;
    if (cnt == M)
    {
        copy();
        spreadVirus();
        return ;
    }
    selected[size + 1] = 1;
    permutation(size + 1, cnt + 1);
    selected[size + 1] = 0;
    permutation(size + 1, cnt);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    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)
                virus.push_back(make_pair(i, j));
            if (map[i][j] == 1)
                map[i][j] = -1;
            map_c[i][j] = map[i][j];
        }
    for (int i = 0; i < virus.size() - M + 1; i++)
    {
        selected[i] = 1;
        permutation(i, 1);
        selected[i] = 0;
    }
    
    if (ans == 2e9)
        cout << "-1\n";
    else
        cout << ans << "\n";
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!