반응형

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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

 

 

[ 문제풀이 ]

 

재귀 함수를 통해서 벽을 세우고 bfs를 이용하여 바이러스를 퍼뜨린 후 안전 영역의 크기를 구해주면 되는 문제입니다.

 

맵의 최대 크기는 8 X 8 이므로 벽을 세우는데 최대 O(64*63*62)의 시간이 걸리므로 모든 경우의 수를 다 탐색하더라도 2초 내에 충분히 풀 수 있는 문제입니다.

 

[ 소스 코드 ]

 

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[8][8];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { -1,1,0,0 };
int ans;
 
struct pos {
    int y;
    int x;
};
 
int bfs(int map[][8])        //바이러스를 퍼트린 후 안전 영역의 크기를 출력
{
    queue<pos>q;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 2) {
                q.push({ i,j });
            }
        }
    }
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (map[yy][xx] == 0) {
                    map[yy][xx] = 2;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
void dfs(int level, int num)        //벽을 세우기 위한 재귀함수
{
    if (level == 3) {            //벽이 3개라면
        int temp[8][8] = { 0 };
        for (int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                temp[i][j] = arr[i][j];
            }
        }
 
        int cnt = bfs(temp);
 
        if (ans < cnt) {
            ans = cnt;
        }
 
        return;
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (N * i + j > num) {        //이전에 벽을 세운 곳 다음부터 탐색
                if (arr[i][j] == 0) {
                    arr[i][j] = 1;
                    dfs(level + 1, i * N + j);
                    arr[i][j] = 0;
                }
            }
        }
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
 
    dfs(0, -1);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2096번 - 내려가기 (C++)  (0) 2022.07.08
[ 백준 ] 5639번 - 이진 검색 트리 (C++)  (0) 2022.07.07
[ 백준 ] 2357번 - 최솟값과 최댓값 (C++)  (0) 2022.07.05
[ 백준 ] 2042번 - 구간 합 구하기 (C++)  (0) 2022.07.04
[ 백준 ] 1019번 - 책 페이지 (C++)  (0) 2022.07.03

+ Recent posts

티스토리툴바