반응형

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

 

17141번: 연구소 2

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 연구소를 입력받을 때 벽을 -1로 바꾸고 바이러스의 위치를 vector에 따로 저장한 후 0으로 바꿉니다.

 

2. 재귀함수를 통해 바이러스를 놓을 위치를 정하고 바이러스를 다 놓은 후 bfs를 통해 바이러스가 모두 퍼질 때까지 걸린 시간을 ans에 저장합니다.

 

3. ans의 값 중 가장 작은 값을 출력합니다.

 

4. 만약 어떠한 경우에도 바이러스를 모두 퍼뜨릴 수 없다면 -1을 출력합니다.

 

[ 소스코드 ]

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
104
105
106
107
108
109
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[50][50];
vector<pair<int, int>> virus;
int pos[10];
int ans = 987654321;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int bfs()
{
    queue<pair<int, int>>q;
    int ret = 0;
    int cnt = 0;
 
    int temp[50][50] = { 0 };
    int visited[50][50] = { 0 };
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    for (int i = 0; i < M; i++) {
        int y = virus[pos[i]].first;
        int x = virus[pos[i]].second;
        q.push({ y,x });
        visited[y][x] = 1;
    }
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        ret = max(ret, temp[y][x]);
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (visited[yy][xx] != 1 && temp[yy][xx] != -1) {
                    visited[yy][xx] = 1;
                    temp[yy][xx] = temp[y][x] + 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (temp[i][j] == 0) cnt++;
        }
    }
 
    if (cnt > M) {
        ret = 987654321;
    }
 
    return ret;
}
 
void dfs(int level, int n)
{
    if (level == M) {
        ans = min(ans, bfs());
        return;
    }
 
    for (int i = n; i < virus.size(); i++) {
        pos[level] = i;
        dfs(level + 1, i + 1);
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 2) {
                virus.emplace_back(i, j);
                arr[i][j] = 0;
            }
            else if (arr[i][j] == 1) {
                arr[i][j] = -1;
            }
        }
    }
 
    dfs(0, 0);
 
    if (ans == 987654321) {
        printf("-1");
    }
    else {
        printf("%d", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 14226번 - 이모티콘 (C++)  (0) 2023.01.08
[ 백준 ] 2470번 - 두 용액 (C++)  (0) 2023.01.07
[ 백준 ] 1275번 - 커피숍2 (C++)  (0) 2023.01.05
[ 백준 ] 10868번 - 최솟값 (C++)  (0) 2023.01.04
[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03

+ Recent posts

티스토리툴바