[BOJ] 17142 - 연구소 3

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

17142번: 연구소 3

 

난이도

구현 + bfs + dfs / 난이도 ⭐️⭐️/ 1시간 20분

 

주의할 점1

핵심은 1) bfs로 M개의 바이러스를 선택한 후, dfs를 수행하는 것이 아니라,

2) bfs로 모든  바이러스를 퍼트린 결과를 저장해둔뒤, dfs를  수행해야한다.

 

1) 방법으로 했을때는 같은 바이러스에 대해 dfs를 중복으로 수행하게 되므로 시간이 더 오래걸린다.

 

예전에 풀었던 방법이 생각나서 2) 방법으로 풀수있었던 것 같다. 예전에  풀었을때는 1)로 풀었다가 시간초과가 났던걸로 기억한다.

 

주의할 점 2

또 한가지 주의할 점은

" 활성바이러스가 비활성바이러스 자리로가면, 비활성 바이러스가 활성 바이러스로 변한다." 조건이다. (코드의 check point1참고)

해당  부분을 처리해주지 않아도 문제에 주어진 테스트 케이스를 모두 통과할 수 있으나 결과 제출 시, 82%에서 틀렸습니다. 가 뜬다.

 

// 82퍼에서 틀림.
#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>
#define INF 1000000000
using namespace std;

int N, M;
int board[51][51] = {0};
int board2[10][51][51] = {0};
vector<pair<int, int> > virus;
int dirx[4] = {-1, 0, 1, 0};
int diry[4] = {0, 1, 0, -1};
int result;

int get_time(vector<int> &activate_virus)
{
    int check[51][51] = {0};
    int virus_index;
    for (int t = 0; t < activate_virus.size(); t++)
    {
        virus_index = activate_virus[t];
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (board[i][j] == 1 || board[i][j] == 2)
                    continue;

                if (virus_index == 0)
                {
                    check[i][j] = board2[virus_index][i][j];
                    continue;
                }
                else
                {
                    if (check[i][j] == 0)
                    {
                        check[i][j] = board2[virus_index][i][j];
                    }
                    else
                    {
                        if (board2[virus_index][i][j] != 0 && board2[virus_index][i][j] < check[i][j])
                        {
                            check[i][j] = board2[virus_index][i][j];
                        }
                    }
                }
            }
        }
    }

    int max_num = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (board[i][j] == 1 || board[i][j] == 2)
                continue;

            if (check[i][j] == 0)
            {
                return -1;
            }

            if (check[i][j] > max_num)
            {
                max_num = check[i][j];
            }
        }
    }

    return max_num;
}

void dfs(vector<int> &activate_virus, int index)
{
    if (activate_virus.size() == M)
    {
        int time;
        time = get_time(activate_virus);
        // printf("time: %d\n", time);
        if (time != -1)
        {
            if (time < result)
            {
                result = time;
            }
        }

        return;
    }

    for (int i = index; i < virus.size(); i++)
    {
        if (virus[i].first == -1)
            continue;

        int tempx = virus[i].first;
        virus[i].first = -1;

        activate_virus.push_back(i);
        dfs(activate_virus, i + 1);
        activate_virus.pop_back();

        virus[i].first = tempx;
    }
}

void bfs(int virus_index, int virusx, int virusy)
{
    bool check[51][51] = {false};
    queue<pair<int, int> > q;

    q.push(make_pair(virusx, virusy));
    board2[virus_index][virusx][virusy] = 0;
    check[virusx][virusy] = true;

    int x, y, newx, newy, num;
    while (!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        num = board2[virus_index][x][y];
        q.pop();

        for (int j = 0; j < 4; j++)
        {
            newx = x + dirx[j];
            newy = y + diry[j];

            if (newx < 0 || newy < 0 || newx > N - 1 || newy > N - 1)
                continue;

            if ((board[newx][newy] == 0 || board[newx][newy] == 2) && !check[newx][newy]) // check point 1) 활성바이러스가  비활성바이러스 자리로가면, 비활성 바이러스가 활성 바이러스로 변한다.
            {
                q.push(make_pair(newx, newy));
                board2[virus_index][newx][newy] = num + 1;
                check[newx][newy] = true;
            }
        }
    }
}

void virus_spread()
{
    int x, y;
    for (int i = 0; i < virus.size(); i++)
    {
        x = virus[i].first;
        y = virus[i].second;
        bfs(i, x, y);
    }
}

int main()
{
    result = INF;
    scanf("%d %d", &N, &M);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &board[i][j]);
            if (board[i][j] == 2)
            {
                virus.push_back(make_pair(i, j));
            }
        }
    }

    virus_spread();
    vector<int> activate_virus;
    dfs(activate_virus, 0);
    if (result == INF)
    {
        printf("-1");
    }
    else
    {
        printf("%d", result);
    }
}