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

 

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고

www.acmicpc.net

바이러스의 위치들을 저장해놓고 활성할 바이러스를 부르트포스로 정하여 bfs로 바이러스가 퍼지는 최소 시간을 구하는 문제입니다.

바이러스가 모두 퍼졌는지에 대한 확인은 처음 0의 갯수(zero) == 전염된 0의 갯수(viruson)으로 확인하였고,

7번 예제와 같이 입력 값으로 빈칸이 주어지지 않은 경우에는

예외처리로 벽의 갯수(wall) + 바이러스의 위치(virus.size()) == N*N으로 확인하였습니다.

마지막에 비활성화 바이러스만 남아도 모두 전염된 것으로 보기 때문에 d배열에서 해당 위치가 빈칸일 경우에만 시간비교를 하였습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
 
vector<pair<int, int> > virus, op;
int list[50][50], d[50][50], N, M, ans = -1, wall, viruson, zero;
int direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
bool visit[50][50], chk[10];
 
void bfs() {
    memset(d, 0, sizeof(d));
    memset(visit, false, sizeof(visit));
    viruson = 0;
 
    int virusoff = virus.size() - M;
    queue<pair<pair<int, int>, int> > q;
    for (int i = 0; i < op.size(); i++) {
        q.push({ op[i], 0 });
        visit[op[i].first][op[i].second] = true;
    }
 
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (list[nx][ny] == 1 || visit[nx][ny]) continue;
 
            q.push({ {nx,ny},cnt + 1 });
            visit[nx][ny] = true;
            d[nx][ny] = d[x][y] + 1;
            if (list[nx][ny] == 0) viruson++;
        }
    }
 
    if (zero == viruson) {
        int movetime = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (list[i][j]) continue;
 
                movetime = max(movetime, d[i][j]);
            }
        }
 
        if (ans == -1) ans = movetime;
        else ans = min(ans, movetime);
    }
}
 
void func(int idx, int cnt) {
    if (cnt == M) {
        bfs();        
        return;
    }
 
    for (int i = idx; i < virus.size(); i++){
        if (chk[i]) continue;
 
        op.push_back(virus[i]);
        chk[i] = true;
        func(i + 1, cnt + 1);
        chk[i] = false;
        op.pop_back();
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
            if (list[i][j] == 2) {
                virus.push_back({ i,j });
            }
            else if (list[i][j]) {
                wall++;
            }
            else zero++;
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    if (wall + virus.size() == N*N) ans = 0;
    else func(0, 0);
    cout << ans << '\n';
 
    return 0;
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 20419 화살표 미로 (Easy)  (0) 2021.01.23
boj 2638 치즈  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22
boj 3055 탈출  (0) 2021.01.22

+ Recent posts

티스토리툴바