[ BOJ - 17142번 ] 연구소 3 (C++)

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

시간제한이 0.25초로 짧았으나, 2차원 배열의 최대 크기가 50x50 = 250이고 바이러스의 최대 개수가 10개이기 때문에 10개 중 M개를 고르는 경우의 최대값은 ₁₀C₅ = 252이기 때문에, 모든 조합에 대해 BFS로 탐색해도 시간초과가 발생하지 않을 것이라 생각했다.

 

[ 풀이 방법 ]

1. 재귀 함수를 이용해 문제에서 제시된 바이러스의 위치 중 M개를 골라 저장한다.

2. M개의 위치를 모두 우선순위 큐에 넣고 BFS를 시작한다.

  - 바이러스가 확산된 시간 순서대로 탐색될 수 있도록 우선순위 큐를 사용했다.

  - 2차원 배열을 만들고 -1로 초기화 한 뒤, 바이러스가 확산되어 각 칸에 도착할 때까지 걸린 시간을 저장했다.

3. BFS가 종료된 후 2차원 배열을 확인하여, 배열에서 가장 큰 값과 다른 바이러스 조합을 탐색하여 저장한 최소 시간을 비교하여 최소 시간을 갱신한다.

  - 벽이 아니면서 초기화 값(-1)이 저장된 경우 최소 시간을 갱신하지 않는다(모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우이기 때문).

 

 구현 중 발생한 변수

1. 바이러스의 좌표와 확산 거리를 저장하는 구조체 Cord를 만들고, priority queue의 emplace()를 사용하기 위해 생성자를 정의하였다.

생성자에 explicit 키워드를 사용해 원하지 않은 형변환이 일어나지 않도록 제한하려 하였으나, Xcode에서는 컴파일 에러가 발생하지 않았지만 문제 제출 시 컴파일 에러가 발생하여 키워드를 빼주었다.

 

2. 바이러스가 확산될 다음 위치에 비활성 바이러스가 있는 경우 확산 시간을 늘리지 않고 그대로 저장해 주었으나, 마지막으로 확산되는 위치가 빈 칸인지, 비활성 바이러스가 있는 칸인지에 따라 결과가 다르게 나왔고,

따라서, priority queue에는 dist+1로 확산 시간을 1 늘려 저장하고 2차원 배열에는 dist를 그대로 저장하여 이 문제를 해결하였다.

 

3. 활성 바이러스와 인접한 비활성 바이러스가 여러개이고, 확산될 위치가 모두 비활성 바이러스인 경우에 0이 결과가 되어야하지만 위 방법을 사용할 경우 올바른 결과가 나오지 않았다. 따라서 priority queue에는 dist+1, 2차원 배열에는 0을 저장하여 문제를 해결하였다.

 

 

 위 방법으로 문제를 모두 해결하였으나 98%에서 "틀렸습니다"를 받았다.

짧은 시간 내에 예외 상황을 찾을 수 없을 것 같아 질문 게시판에 있는 반례를 보고 문제를 찾을 수 있었다.

4 1
1 1 1 1
1 2 1 1
1 1 1 1
1 1 2 0

 위 입력이 주어질 경우, 비활성 바이러스가 벽에 둘러쌓여 값이 0으로 갱신되지 못해 초기화 값인 -1이 저장된 상태로 남게된다.

따라서 BFS 함수가 실행될 때가 아니라 2차원 배열을 체크하여 최대값을 구할 때 비활성 바이러스가 있는 위치를 0으로 할당해주어 문제를 해결할 수 있었다.

(2차원 배열 체크 시에 바이러스가 있는 위치는 최소 시간을 갱신하지 않고 생략하는 방식으로 구현할 경우, 새롭게 바이러스가 확산된 칸이 없이 비활성 바이러스가 있던 칸만 있는 경우 올바르게 처리되지 않는다.)

 

[ 회고 ]

 비활성 바이러스가 있는 위치를 방문하지 못하는 경우를 생각하지 못해서 정답을 맞추지 못했다. 벽에 둘러쌓여 있는 빈칸이 있는 경우 방문하지 못해 초기화된 값이 저장되어 있을 것이라는 생각은 할 수 있었지만 빈칸이 아니라 비활성 바이러스가 갇혀있는 경우는 생각하지 못했다. 문제의 조건 중 특이한 사항이 활성 바이러스와 비활성 바이러스로 나뉘는 부분이었는데 이 부분에 대해 깊게 생각하지 않고 넘어갔던 것 같다.

 

 앞으로 이런 유형의 문제를 풀 때에는 문제에서 유의해야 할 조건을 미리 파악하고 벽에 둘러쌓여 있어 방문하지 못하는 경우에 발생할 수 있는 변수들에 대해 파악하여, 예외 상황이 발생했을 때 그 부분을 유의하여 살펴봐야 할 것 같다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>

#define EMPTY 0
#define WALL 1
#define VIRUS 2

using namespace std;

const int INF = 1<<30;

struct Cord {
    int x; int y;
    int dist;
    
    Cord(int x, int y, int dist) : x(x), y(y), dist(dist) {}
    Cord(const Cord& cord) : x(cord.x), y(cord.y), dist(cord.dist) {}
};

struct cmp {
    bool operator()(const Cord& cord1, const Cord& cord2){
        return cord1.dist > cord2.dist;
    }
};

int N, M;
vector<vector<int>> board;
vector<Cord> cords;

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, -1, 0, 1};

int res = INF;

void bfs(vector<Cord>& choice, vector<vector<int>>& virus) {
    
    priority_queue<Cord, deque<Cord>, cmp> pq;
    for (int i = 0; i < int(choice.size()); i++) {
        pq.emplace(choice[i]);
        virus[choice[i].x][choice[i].y] = 0;
    }

    while (!pq.empty()) {

        int x = pq.top().x;
        int y = pq.top().y;
        int dist = pq.top().dist;
        pq.pop();

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dirX[dir];
            int ny = y + dirY[dir];

            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(board[nx][ny] == WALL || virus[nx][ny] >= 0) continue;

            pq.emplace(nx, ny, dist+1);
           
            virus[nx][ny] = dist+1;
        }
    }
}

void check(vector<vector<int>>& virus) {
    
    int maxValue = -1;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(board[i][j] != WALL) {
                if(board[i][j] == VIRUS) virus[i][j] = 0;
                if(virus[i][j] == -1) {
                    return;
                }
                maxValue = max(maxValue, virus[i][j]);
            }
        }
    }
    
    res = min(res, maxValue);
}

void rec(int idx, vector<Cord>& choice) {
    if(int(choice.size()) == M) {
        vector<vector<int>> virus(N, vector<int>(N, -1));
        bfs(choice, virus);
        check(virus);
        vector<vector<int>>().swap(virus);
    }
    
    for (int i = idx; i < int(cords.size()); i++) {
        choice.emplace_back(cords[i]);
        rec(i+1, choice);
        choice.pop_back();
    }
}

void solve() {
    vector<Cord> choice;
    rec(0, choice);
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    board.resize(N, vector<int>(N));
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if(board[i][j] == 2) {
                cords.emplace_back(i, j, 0);
            }
        }
    }
    
    solve();
    
    if(res == INF) cout << -1 << '\n';
    else cout << res << '\n';
    
    return 0;
}