[BOJ 17142] 연구소3

문제출처

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

17142번: 연구소 3

 

문제풀이

연구소에 이어 조금 예외가 추가된 문제이다. 기본적으로는 완전탐색을 통해 풀면 된다 생각되었다.

소스코드 작성에 앞서 문제 풀이 방법은 다음과 같이 생각해봤다.

1. 활성화할 바이러스를 선택한다(selectVirus)

- 선택한 바이러스가 m개라면 바이러스를 퍼트린다.

2. 바이러스를 퍼뜨릴때 모든 경우를 다 사용해야 하기 때문에 새로운 2차원 배열을 생성한다.

- 활성화할 바이러스를 큐에 담는다.

- 문제에서 제시한 조건을 따라 벽이거나 이미 바이러스가 전파된 경우를 제외하고 바이러스를 전파한다.

3. 활성화된 바이러스로 퍼지는데 걸리는 시간을 구한다.

- 이때 입력으로 받은 map이 빈칸이고 새로운 timeMap이 초기 값이라면 바이러스가 완전히 퍼지지 않은것으로 판단한다.

- 활성화된 바이러스는 제외해야하기 때문에 map이 0인 것만 카운팅한다.

4. 이후 return 받은 결과값이 최대값과 같다면 바이러스를 모든 빈 칸에 전파할 수 없는 경우이므로 -1을 출력하고 이외의 경우 최소값을 출력한다.

 

생각보다 시간이 많이 걸렸다. 처음 90%대에서 자꾸 틀렸습니다가 나왔는데 활성화된 바이러스를 제외하지 않아서 였다. 백준 게시판의 반례모음집을 보고 어디서 잘못됬는지 파악할 수 있었다.

소스 작성전에 예외없이 알고리즘을 짤 수 있도록 습관을 더 길러야겠다.

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
// 2020/04/12 14:55 문제풀이 시작 -> 16:40 문제풀이 완료
struct VIRUS {
    int y, x;
};
bool isAllSpread;
int n, m, ans=987654321;
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int map[50][50];
vector<VIRUS> virus, selected;
void init() {
    cin>>n>>m;
    for (int y=0; y<n; y++) {
        for (int x=0; x<n; x++) {
            cin>>map[y][x];
            if (map[y][x] == 2) virus.push_back({y,x});
        }
    }
}
int spreadVirus() {
    isAllSpread = 1;
    queue<VIRUS> q;
    int timeMap[50][50];
    memset(timeMap, -1, sizeof(timeMap));

    for (int i=0; i<selected.size(); i++)  {
        q.push(selected[i]);
        timeMap[selected[i].y][selected[i].x] = 0;
    }

    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();

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

            // out of bound
            if (ny<0 || nx<0 || ny>=n || nx>=n) continue;

            // 벽 or 이미 바이러스 퍼진 경우
            if (map[ny][nx] == 1 || timeMap[ny][nx] != -1) continue;

            q.push({ny, nx});
            timeMap[ny][nx] = timeMap[y][x] + 1;
        }
    }

    int time=0;
    for (int y=0; y<n; y++) {
        for (int x=0; x<n; x++) {

            // 전부 전파하지 못한 경우
            if (map[y][x] == 0 && timeMap[y][x] == -1) {
                isAllSpread=0;
                return 987654321;
            }
            // 활성화 하지 않은 바이러스는 제외
            else if (map[y][x] == 0) {
                time = max(time, timeMap[y][x]);
            }
        }
    }
    return time;
}
void selectVirus(int index) {
    if (selected.size() == m) {
        int time = spreadVirus();
        if (isAllSpread) ans = min(ans, time);

        return;
    }

    for (int i=index; i<virus.size(); i++) {
        selected.push_back(virus[i]);
        selectVirus(i+1);
        selected.pop_back();
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    selectVirus(0);
    if (ans == 987654321) cout<<"-1"<<"\n";
    else cout<<ans<<"\n";
    return 0;
}