문제 URL : https://www.acmicpc.net/problem/2638
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로
www.acmicpc.net
문제 접근법 :
단순한 구현문제입니다. 치즈는 반드시 언젠가는 사라지게되있습니다.
좌우상하 공기중에 2군대이상 접촉하는지 확인하는 문제이기때문에 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
|
#include<bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
int n, m;
vvi board;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void input() {
cin >> n >> m;
board = vvi(n + 2, vi(m + 2));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> board[i][j];
}
}
}
bool isrange(int y, int x) {
return 0 <= y && y< n + 2 && 0 <= x && x < m + 2;
}
void solve() {
int res = 0;
bool flag=false;
do {
queue<pair<int, int>> q;
q.push({ 0,0 });
vvi check(n + 2, vi(m + 2)), melt(n + 2, vi(m + 2));
check[0][0] = 1;
flag = false;
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx)) {
if (board[ny][nx])
melt[ny][nx]++;
if (board[ny][nx] == 0 && check[ny][nx] == 0) {
q.push({ ny,nx });
check[ny][nx] = 1;
}
}
}
}
for(int i=1;i<=n;i++){
for (int j = 1; j <= m; j++) {
if (melt[i][j] >= 2) {
flag = true;
board[i][j] = 0;
}
}
}
res += flag;
} while (flag);
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는 점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 9328 열쇠 (0) | 2022.03.29 |
|---|---|
| 백준 17140 이차원 배열과 연산 (0) | 2022.03.29 |
| 백준 6198 옥상 정원 꾸미기 (0) | 2022.03.22 |
| 백준 16724 피리 부는 사나이 (0) | 2022.03.22 |
| 백준 17298 오큰수 (0) | 2022.03.20 |
