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

얻어갈 게 많은 BFS 문제. 시간초과에 어떻게 대응할지 고민하는 시간이었다.

문제

문제에서 추출할 수 있는 정보는 다음과 같다.

• 최소가 되는 시간을 찾아야 한다.
• 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 참고로 놓을 수 있는 칸임에도 놓지 않았다면 빈 칸으로 간주된다.

입출력

추가적인 조건을 확인할 수 있다.

• 모든 바이러스 배치 case를 살펴봐도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없다면 -1을 출력한다.
• 모든 빈 칸에 바이러스를 퍼뜨릴 수 없다 -> visited가 false면서 0인 좌표가 존재한다.
• 입출력이 불친절한 문제이다. 벽에 대한 정보를 1 말고 -1로 주면 더 편했을 텐데

• 입출력에서 우리는 2를 받았을 때 2가 있는 좌표를 저장하면서 2를 0으로 바꾸어 저장하였고, 1을 받았을 때 1이 벽임을 표기해야 한다. 나는 -1로 바꾸어주었다.
• 예시를 확인해보면, 2가 입력된 모든 칸은 일단 맵 상에서 0이어야 함을 알 수 있다. 2인 채로 대처하려 하면 "2초" 와 혼동되기 때문이다.

이 문제는 크게 2가지를 처리해야 한다.

• n개의 바이러스 후보 중 m개 좌표를 선택하여 바이러스 투입(nCm)
• m개 좌표가 큐에 저장된 상태로 BFS

첫번째 문제로 시간초과가 발생할 가능성이 매우 높았다.

이때 반환해야 하는 값은 "빈칸을 모두 감염시키는데 성공한 case 중 가장 적게 걸린 시간"이다. 여기서 맵에서 가장 큰 숫자가 마지막으로 전염시킨 시간이 되므로, 성공 case의 맵 값 중 가장 큰 값을 저장한 뒤, 이 큰 값 중 가장 적은 값을 반환하면 된다. 말이 좀 어렵다.

그렇다면 실패한 case는 무엇일까? 앞서 언급했다시피 실패 조건은 0인데 아직 방문하지 않은 map 좌표가 존재할 때이다. 이 경우 -1을 반환해야 한다.
이를 반영한 BFS 코드는 위와 같다.

그렇다면 이제 어떻게 nCm을 구현할 수 있을까? 먼저 백트래킹으로 구현한 나의 첫번째 코드는 아래와 같다.

for문을 살펴보자. 저 for문의 문제점은, 예를 들어 m=3일 때 (1번 좌표, 2번 좌표, 3번 좌표)를 처음에 선택했을 때, i가 0부터 시작하기 때문에 (3번 좌표, 1번 좌표, 2번 좌표)나 (2번 좌표, 1번 좌표, 3번 좌표)와 같은 case가 중복되어 계산된다. nCm을 원하는데, 의도치 않게 nPm이 된 것이다.

실제로 디버깅을 해보면 이 코드의 문제점을 알 수 있다.
예제 1의 디버깅 결과이다.
0 0 1 5 4 3
1 5 0 0 4 3 이 보이는가?

이미 선택했던 결과를 선택 순서만 바꾸어서 반복하고 있다.

수정된 코드는 위와 같다. 이제 디버깅 결과를 살펴보자.

중복되는 케이스가 소멸한 것을 알 수 있다.
nCm과 nPm의 구현 차이에 대해서 제대로 알아야 한다는 교훈을 안겨준 문제였다.

소스 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;
int n, m;
vector<pair<int, int> > v; // 바이러스 배치 후보 명단
int map[51][51]; // 사용될 배열
int origin[51][51]; // 원본 배열
bool visited[51][51]; // 방문 여부
vector<pair<int, int> > vv; // 선택한 바이러스 위치
bool visit_v[11]; // 바이러스 위치 선택 여부
int ans = 999;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int BFS(vector<pair<int, int> > pos){
    queue<pair<int, int> > q;
    int cnt = 0;
    for(int i=0; i<pos.size(); i++){ // 최초 바이러스 위치 방문처리하고 큐에 담기
        q.push(make_pair(pos[i].first, pos[i].second));
        visited[pos[i].first][pos[i].second] = true;
    }

    while(!q.empty()){ // BFS
        int x = q.front().first;
        int y = q.front().second;

        q.pop();
        if(map[x][y] > cnt){ // 가장 큰 맵의 숫자 -> 마지막으로 전염시킨 위치가 된다.
            cnt = map[x][y];
        }

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(visited[nx][ny] || map[nx][ny] == -1) continue;
            if(!visited[nx][ny] && map[nx][ny] == 0){
                map[nx][ny] = map[x][y] + 1;
                q.push(make_pair(nx, ny));
                visited[nx][ny] = true;
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(map[i][j] == 0 && !visited[i][j]){ // 실패 조건
                return -1;
            }
        }
    }
    return cnt;
}

void copys(){ // 원본 배열로 초기화
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            map[i][j] = origin[i][j];
        }
    }
}

void DFS(int idx, int cnt){
    if(cnt == m){ // m개 선택했다면
        memset(visited, false, sizeof(visited));
        copys(); // 각 선택의 경우마다 맵과 방문여부를 초기화해야한다.

        int cnt = BFS(vv);
        if(cnt != -1){ // -1이면 실패이므로 배제한다.
            ans = min(ans, cnt);
        }
        return;
    }

    for(int i=idx; i<v.size(); i++){ // 백트래킹 방식으로 nCm을 구현한다.
        if(visit_v[i]) continue;
        visit_v[i] = true;
        vv.push_back(v[i]);
        DFS(i + 1, cnt + 1);
        visit_v[i] = false;
        vv.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i=0;  i<n; i++){
        for(int j=0; j<n; j++){
            cin >> origin[i][j];
            if(origin[i][j] == 2){
                origin[i][j] = 0; 
                v.push_back(make_pair(i, j)); // 바이러스 후보군에 담는다.
            } else if(origin[i][j] == 1){
                origin[i][j] = -1;
            }
        }
    }

    DFS(0, 0);

    if(ans == 999) ans = -1; // 모든 case가 실패했다면 초기값인 999이므로
    cout << ans;
    return 0;
}

교훈

• nCm을 구현해야 할 때, 시간초과가 난다면 중복으로 카운트되는 것이 없는지 DFS for문을 주의깊게 검토하자.
• nCm과 nPm은 구현에서 차이가 있다. 확실하게 이해하고 넘어가자.
• BFS는 신속함과 정확함이 생명이다.
• 코드 치기 전 문제와 입출력을 제대로 읽으면서 내가 이해했는지 체크해야 한다.