[Algorithm] Baekjoon 17142번 : 연구소 3

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

17142번: 연구소 3

 
struct Node
{
    int y;
    int x;
    int turn = 0;
};
 
int n, m;
int arr[51][51] = { 0 };
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int targetCount = 0;
 
vector<Node> viruses;
vector<int> virusIndexes;
 
int BFS()
{
    bool visited[51][51] = { false };
    int answerCount = 0;
 
    queue<Node> q;
    for (int i = 0; i < m; ++i)
    {
        q.push({ viruses[virusIndexes[i]] });
        visited[viruses[virusIndexes[i]].y][viruses[virusIndexes[i]].x] = true;
    }
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curTurn = q.front().turn;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
 
            if (nextY < 0 || nextY == n) continue;
            if (nextX < 0 || nextX == n) continue;
            if (visited[nextY][nextX]) continue;
            if (arr[nextY][nextX] == 1) continue;
            
            if (arr[nextY][nextX] == 0)
            {
                ++answerCount;
            }
 
            if (answerCount == targetCount)
            {
                return curTurn + 1;
            }
 
            visited[nextY][nextX] = true;
            q.push({ nextY,nextX, curTurn + 1 });
        }
    }
 
    return 0x3f3f3f3f;
}
 
vector<int> answers;
 
void DFS(int index, int count)
{
    if (count == m)
    {
        answers.push_back(BFS());
    }
 
    for (int i = index + 1; i < viruses.size(); ++i)
    {
        virusIndexes.push_back(i);
        DFS(i, count + 1);
        virusIndexes.pop_back();
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
 
            if (arr[i][j] == 0)
            {
                ++targetCount;
            }
 
            if (arr[i][j] == 2)
            {
                viruses.push_back({ i,j });
            }
        }
    }
 
    if (targetCount == 0)
    {
        cout << 0;
        return 0;
    }
 
    DFS(-1, 0);
 
    sort(answers.begin(), answers.end());
 
    if (answers[0] == 0x3f3f3f3f) cout << -1;
    else cout << answers[0];
}

 

브루트포스 + 시뮬레이션 문제라고 할 수 있다.

 

전부 바이러스로 감염시키는데 필요한 최소시간을 구해야하는데, 바이러스 위치를 전부 뽑아줘야된다.

비활성화 바이러스개수중에서 m개만큼을 뽑고, 그걸로 BFS를 활용해서 시뮬레이션하면 된다.

input값은 작긴한데, 그렇다고 왠지 매 BFS마다 tempArr에다가 arr을 복사하는식으로 하면 시간제한걸릴 것 같아서 그렇게 안하도록 작성했다.

 

빈공간 없이 벽만 있거나, 비활성화바이러스 ( 값 2로 주어지는것)만 있다면, 퍼뜨릴필요가 없으니 0을 출력해야한다는것만 인지하자.