BOJ 17141 [연구소 2]

BOJ 연구소 2 : www.acmicpc.net/problem/17141

17141번: 연구소 2

옛날에 연구소는 풀어봤는데, 2탄도 있는줄 몰랐다.

나의 풀이 방법은 다음과 같다.

1. 바이러스를 놓을 수 있는 구역을 먼저 체크해 vector에 담아놓는다.
2. 브루트 포스를 이용해 바이러스를 놓는 모든 경우의 수를 체크한다.
3. BFS로 바이러스를 확산시켜본다.

제출하니 420ms나 걸린다...

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
struct Node
{
    int x;
    int y;
    int depth;
public:
    Node(int x, int y, int depth)
    {
        this->x = x;
        this->y = y;
        this->depth = depth;
    }
};
 
struct Point
{
    int x;
    int y;
public:
    Point(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
};
 
int N, M;
 
int result = 999999;
 
int lab[50][50];
int corona[50][50];
 
 
bool visited[50][50];
int dx[] = { -1,0,0,1 };
int dy[] = { 0,-1,1,0 };
 
queue<Node> q;
vector<Point> selectedPoint;
vector<Point> virusPoint;
 
void InitializeVisit()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            visited[i][j] = false;
        }
    }
}
 
void InputVirus()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> lab[i][j];
            
            if(lab[i][j] == 2)
            {
                virusPoint.push_back(Point(i, j));
            }
        }
    }
}
 
void CopyLab()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            switch (lab[i][j])
            {
            case 1:
                corona[i][j] = -1;
                break;
            case 0:
            case 2:
                corona[i][j] = 0;
                break;
            }
        }
    }
}
 
bool IsBoundary(int x, int y)
{
    return x >= 0 && x < N && y >= 0 && y < N;
}
 
int GetResult()
{
    int time = 0;
 
    CopyLab();
 
    for (int i = 0; i < selectedPoint.size(); i++)
    {
        int x = selectedPoint[i].x;
        int y = selectedPoint[i].y;
 
        corona[x][y] = 1;
        
        q.push(Node(x, y, 0));
    }
 
    while (!q.empty())
    {
        Node node = q.front();
        q.pop();
        
        time = node.depth;
 
        for (int j = 0; j < 4; j++)
        {
            int nextX = node.x + dx[j];
            int nextY = node.y + dy[j];
            if (IsBoundary(nextX, nextY) && corona[nextX][nextY] == 0)
            {
                corona[nextX][nextY]++;
                q.push(Node(nextX, nextY, node.depth + 1));
            }
        }
    }
    return time;
}
 
bool EmptyCheck()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (corona[i][j] == 0)
            {
                return false;
            }
        }
    }
    return true;
}
 
void SelectPoint(int depth, int index)
{
    if (depth == M || index == N * N)
    {
        int time = GetResult();
        
        if (EmptyCheck())
        {
            if (time <= result)
            {
                result = time;
            }
        }
        return;
    }
    int size = virusPoint.size();
    for (int i = index; i < size; i++)
    {
        int x = virusPoint[i].x;
        int y = virusPoint[i].y;
        
        selectedPoint.push_back(Point(x, y));
        SelectPoint(depth + 1, i + 1);
        selectedPoint.pop_back();
        SelectPoint(depth, i + 1);
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    InputVirus();
 
    SelectPoint(0, 0);
 
    if (result == 999999)
    {
        result = -1;
    }
 
    cout << result << endl;
    return 0;
}