https://www.acmicpc.net/problem/2140
보드의 테두리에 숫자가 있고, 닫혀있는 칸들 중 지뢰가 최대 몇개 묻혀져 있는지 구하는 문제입니다.
지뢰의 최대 수를 구하면 되기 때문에 닫혀있는 칸들 중 지뢰가 아닌 칸은 숫자라고 생각하시면 되겠습니다.
우선 지뢰가 있으려면 주변에 0이 없어야 합니다.
8방향 탐색으로 0이 있는지 확인하시고, 0이 없다면 지뢰를 묻어주도록 합니다.
지뢰를 묻은 칸은 -1으로 변경해주고, 주변 8방향에 있는 숫자 칸들은 모두 -1을 해줍니다.
-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
|
#include <iostream>
#define MAX 101
using namespace std;
char list[MAX][MAX];
int direct[8][2] = { {1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1} };
int N;
void eraseNum(int x, int y) {
for (int d = 0; d < 8; d++) {
int nx = x + direct[d][0];
int ny = y + direct[d][1];
if (list[nx][ny] == -1 || list[nx][ny] == '#') continue;
list[nx][ny] -= 1;
}
}
void func() {
int ret = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (list[i][j] != '#') continue;
bool flag = true;
for (int d = 0; d < 8; d++) {
int nx = i + direct[d][0];
int ny = j + direct[d][1];
if (list[nx][ny] == '0') {
flag = false;
break;
}
}
if (flag) {
ret++;
list[i][j] = -1;
eraseNum(i, j);
}
}
}
cout << ret << '\n';
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 1437 수 분해 (0) | 2024.07.12 |
|---|---|
| boj 23559 밥 (0) | 2024.07.11 |
| boj 1132 합 (0) | 2024.07.08 |
| boj 25381 ABBC (0) | 2024.07.07 |
| boj 28325 호숫가의 개미굴 (0) | 2024.07.06 |