백준 2638번 : 치즈 / C++
2023. 3. 24. 11:40ㆍ개인공부/코딩테스트
https://www.acmicpc.net/problem/2638
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로
www.acmicpc.net
같은 제목의 치즈를 응용한 문제이다. 치즈를 기준으로 BFS를 도는 경우가 아니라 가장자리부터 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
|
#include <iostream>
#include <queue>
using namespace std;
int N, M; // row , col
int arr[100][100]{};
int tmp[100][100]{};
bool BFS()
{
queue<pair<int, int>> Q;
bool visited[100][100]{};
Q.push(make_pair(0, 0));
visited[0][0] = true;
while (!Q.empty())
{
int Row = Q.front().first;
int Col = Q.front().second;
// up row-1
if (Row > 0 && !visited[Row - 1][Col]) {
if (!arr[Row - 1][Col]) {
Q.push(make_pair(Row - 1, Col));
visited[Row - 1][Col] = true;
}
else
--tmp[Row - 1][Col];
}
// down row+1
if (Row + 1 < N && !visited[Row + 1][Col]) {
if (!arr[Row + 1][Col]) {
Q.push(make_pair(Row + 1, Col));
visited[Row + 1][Col] = true;
}
else
--tmp[Row + 1][Col];
}
// left col-1
if (Col > 0 && !visited[Row][Col - 1]) {
if (!arr[Row][Col - 1]) {
Q.push(make_pair(Row, Col - 1));
visited[Row][Col - 1] = true;
}
else
--tmp[Row][Col - 1];
}
// right col+1
if (Col + 1 < M && !visited[Row][Col + 1]) {
if (!arr[Row][Col + 1]) {
Q.push(make_pair(Row, Col + 1));
visited[Row][Col + 1] = true;;
}
else
--tmp[Row][Col + 1];
}
Q.pop();
}
for (int row = 1; row < N - 1; ++row)
for (int col = 1; col < M - 1; ++col){
if (tmp[row][col] < 0)
arr[row][col] = 0;
}
for (int row = 1; row < N - 1; ++row)
for (int col = 1; col < M - 1; ++col)
if (arr[row][col] == 1)
return false;
return true;
}
void Solve()
{
int ans = 0;
while (true)
{
++ans;
for (int row = 0; row < N; ++row)
for (int col = 0; col < M; ++col)
tmp[row][col] = arr[row][col];
if (BFS()){
cout << ans;
break;
}
}
}
int main()
{
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
cin >> N >> M;
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
cin >> arr[i][j];
Solve();
}
|
cs |
'개인공부 > 코딩테스트' 카테고리의 다른 글
| 백준 11725번 : 트리의 부모 찾기 / C++ (0) | 2023.03.27 |
|---|---|
| 백준 4779번 : 칸토어 집합 / C++ (0) | 2023.03.27 |
| 백준 2573번: 빙산 / C++ (1) | 2023.03.24 |
| 백준 2589번 : 보물섬 / C++ (0) | 2023.03.23 |
| 백준 11657번 : 타임머신 / C++ (0) | 2023.03.22 |