문제 풀이
이 문제는 바이러스가 퍼지는 부분은 단순한 bfs 문제로 풀이가 가능했지만, 벽을 세우는 부분에서 코드가 길어지다 보니 헷갈리는 부분이 생겼던 문제입니다. 코드를 최대한 단순하게 짜는 것이 실수를 줄이는 방법이 될 것 같습니다..
코드
|
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
110
|
#include <iostream>
#include <queue>
using namespace std;
int n, m;
int room[8][8];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int bfs(queue<pair<int, int>> q) {
int space = 0;
int d[8][8] = { 0, };
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
d[i][j] = room[i][j];
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
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 >= m) continue;
if (d[nx][ny] == 0)
{
d[nx][ny] = 2;
q.push(make_pair(nx, ny));
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (d[i][j] == 0)
space++;
}
}
return space;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ans = 0;
queue<pair<int, int>> q;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> room[i][j];
if (room[i][j] == 2)
q.push(make_pair(i, j));
}
}
for (int i1 = 0; i1 < n; i1++)
{
for (int j1 = 0; j1 < m; j1++)
{
if (room[i1][j1] != 0) continue;
for (int i2 = 0; i2 < n; i2++)
{
for (int j2 = 0; j2 < m; j2++)
{
if (room[i2][j2] != 0) continue;
for (int i3 = 0; i3 < n; i3++)
{
for (int j3 = 0; j3 < m; j3++)
{
if (room[i3][j3] != 0) continue;
if (i1 == i2 && j1 == j2)
continue;
if (i2 == i3 && j2 == j3)
continue;
if (i1 == i3 && j1 == j3)
continue;
room[i1][j1] = 1;
room[i2][j2] = 1;
room[i3][j3] = 1;
int x = bfs(q);
if (x > ans)
ans = x;
room[i1][j1] = 0;
room[i2][j2] = 0;
room[i3][j3] = 0;
}
}
}
}
}
}
cout << ans << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter
|
제출 결과
문제 출처
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
www.acmicpc.net
'algorithm codes > baekjoon online judge' 카테고리의 다른 글
| 14225번: 부분수열의 합 (백준 온라인 저지, C++) (0) | 2019.04.04 |
|---|---|
| 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (백준 온라인 저지, C++) (0) | 2019.04.04 |
| 14500번: 테트로미노 (백준 온라인 저지, C++) (0) | 2019.04.03 |
| 2448번: 별 찍기 - 11 (백준 온라인 저지, C++) (0) | 2019.04.02 |
| 1978번: 소수 찾기 (백준 온라인 저지, C++) (0) | 2019.04.02 |