BOJ 17142 - 연구소 3

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

 

재밌는 문제였다.

 

처음 입력받을 때 바이러스의 위치들을 따로 저장해둔다.

그리고 조합을 구해 어떤 바이러스들을 활성화시킬지 경우의 수를 뽑는다.

뽑힌 경우의 수를 돌며 바이러스를 퍼뜨리기 시작하는데, 이때 bfs를 사용했다.

그런데 일반적인 bfs를 도는 게 아니라, 층을 나눠주는 게 필요하다. 

왜냐하면 큐에 여러개가 들어있는데, 1초가 지났을때, 2초가 지났을 때 이런식으로 구별이 필요하기 때문이다.

그래서 while문 안에서 qSize를 받고, qSize만큼의 반복문이 끝나면 시간이 올라가게끔 구별해줬다.

이걸 무슨 기법이라고 했는데, 이름은 까먹었다. 파티션 뭐 이런거였던 거 같은데

어쨌든 이렇게 해주면서 시간을 비교해 최소시간을 출력해주면 된다.

 

그런데 이 때, 처음에는 남은 빈칸이 있는지 없는지를 확인하기 위해 한 사이클이 다 돌고나면 모든 배열을 돌며 0이 있는지 없는지 확인하는 식으로 짰었다. (아래의 코드에도 흔적이 남아있다. check() 함수)

 

그런데 이렇게 하자 시간초과가 났고, 어떻게 시간을 줄일 수 있을까 고민하다가 처음 입력받을때부터 벽의 수를 저장하고, bfs를 돌때 next가 빈칸이면 빈칸의 수를 줄이는 식으로 해서 빈칸이 0이 되면 반복문을 끝내는 식으로 만들어줬고, 시간복잡도를 통과할 수 있었다.

(50 * 50 = 2500을 몇번을 도는 걸 없애서)

 

#include <bits/stdc++.h>
using namespace std;
int a[54][54];
int cp[54][54];
int n, m;
vector<pair<int, int>> v;
vector<vector<int>> combi;
int mn = 1e9;
int dirY[4] = {1, -1, 0, 0};
int dirX[4] = {0, 0, 1, -1};
int visited[54][54];
int floorCnt = 0;

void print()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << cp[i][j] << " ";
        }
        cout << "\n";
    }
}

void makeCombi(int start, int limit, vector<int> tmp)
{
    if (tmp.size() == limit)
    {
        combi.push_back(tmp);
        return;
    }
    for (int i = start + 1; i < v.size(); i++)
    {
        tmp.push_back(i);
        makeCombi(i, limit, tmp);
        tmp.pop_back();
    }
}

bool check()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (cp[i][j] == 0)
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == 2)
            {
                v.push_back({i, j});
            }
            if (a[i][j] == 0)
            {
                floorCnt++;
            }
        }
    }
    if (floorCnt == 0)
    {
        cout << 0 << "\n";
        return 0;
    }

    makeCombi(-1, m, {});

    for (int i = 0; i < combi.size(); i++)
    {
        copy(&a[0][0], &a[0][0] + 54 * 54, &cp[0][0]);
        memset(visited, 0, sizeof(visited));
        int fCnt = floorCnt;
        // 바이러스 활성화 (3)
        int t = 1;
        queue<pair<int, int>> q;
        for (int j = 0; j < combi[i].size(); j++)
        {
            int idx = combi[i][j];
            int y = v[idx].first;
            int x = v[idx].second;
            cp[y][x] = 3;
            q.push({y, x});
        }
        bool flag = false;
        while (q.size())
        {
            int qSize = q.size();
            for (int i = 0; i < qSize; i++)
            {
                int curY = q.front().first;
                int curX = q.front().second;
                // cout << "curY : " << curY << ", curX : " << curX << "\n";
                q.pop();
                for (int j = 0; j < 4; j++)
                {
                    int nextY = curY + dirY[j];
                    int nextX = curX + dirX[j];
                    if (nextY >= 0 && nextY < n && nextX >= 0 && nextX < n && !visited[nextY][nextX] && (a[nextY][nextX] == 0 || a[nextY][nextX] == 2))
                    {
                        cp[nextY][nextX] = 3;
                        visited[nextY][nextX] = 1;
                        if (a[nextY][nextX] == 0)
                        {
                            fCnt--;
                        }
                        q.push({nextY, nextX});
                    }
                }
            }
            if (fCnt == 0)
            {
                flag = true;
                break;
            }
            t++;
        }
        // cout << "t : " << t << "\n";
        // print();
        // cout << "----------\n";
        if (flag)
        {
            mn = min(mn, t);
        }
    }

    if (mn == 1e9)
    {
        cout << -1 << "\n";
    }
    else
    {

        cout << mn << "\n";
    }
    return 0;
}