728x90
반응형
https://www.acmicpc.net/problem/16918
16918번: 봄버맨
첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.
www.acmicpc.net
|
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
|
#include<stdio.h>
#include<queue>
#define NSIZE 201
#define MSIZE 201
using namespace std;
int N, M,Time;
char input[NSIZE][MSIZE];
int chk[NSIZE][MSIZE];
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Data{
int y,x,time;
};
queue<Data>q;
void init() {
scanf("%d %d %d", &N, &M,&Time);
for (int i = 0; i < N; i++) {
scanf(" %s", input[i]);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (input[i][j] == 'O') {
chk[i][j] = 3;
}
}
}
}
void stay() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(chk[i][j]!=0)
chk[i][j]--;
}
}
}
void install(){
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (chk[i][j] == 0) {
chk[i][j] = 3;
}
else if (chk[i][j] >1) {
chk[i][j]--;
}
}
}
}
void chkbomb() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (chk[i][j] == 1) {
q.push({ i,j });
while (!q.empty()) {
Data c = q.front(); q.pop();
chk[c.y][c.x] = 0;
for (int dir = 0; dir < 4; dir++) {
Data n;
n.y = c.y + dy[dir];
n.x = c.x + dx[dir];
if (n.y<0 || n.y>N || n.x<0 || n.x>M)continue;
if (chk[n.y][n.x] == 1) {
q.push({ n.y,n.x });
}
chk[n.y][n.x] = 0;
}
}
}
if (chk[i][j] > 1) {
chk[i][j]--;
}
}
}
}
int main(void) {
init();
stay();
Time--;
while (Time) {
install();Time--;
if (Time == 0)break;
chkbomb(); Time--;
if (Time == 0)break;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (chk[i][j] == 0) printf(".");
else printf("O");
}
printf("\n");
}
return 0;
}
|
이문제의 핵심은 두 가지입니다. bfs로 폭탄이 터지는 구역을 없애고
문제 그대로 잘짜는것?
정말 이문제는
문제에 나온 것 같이 위에서부터 1 2 3 4인데
1번은 입력이고
2번은 3,4번을 반복하기 전에 한 번만 해주면 되는 것이고
3,4번은 time 4초라면 2번을 수행할 때 1초가 지나기 때문에 3초 안에서 3,4를 해주면 됩니다.
소스 롤 보여드리면
1번은
2번은
3번은
4번은
정말 하라는 대로만 구현해서 하면 됩니다. 다들 해보시고 만약 안 된다 하면 질문해주세요.
4번을 보면 큐에 1인 것을 넣었는데 그 이유는 이전에
별표 인 부분이 먼저 큐로 탐색을 하면서 위에 3과 아래 3과 1을 0으로 만들 수 있는데 큐에 1인걸 넣지 않는다면
별표 옆에 1이 자신도 자기 주변의 방을 0으로 만들어야 하는데 그러지 못하기 때문에 1이면 넣고 그 1도 0을 만드는 것을
수행할 수 있도록 했습니다. 말을 어렵게 해서 그렇지 당연히 그렇게 해야 한다고 느낄 거예요.
무튼 오늘도 여기까지 보시느라 고생 많으셨습니다. 내일도 알 고풀이로 뵙겠습니다.
오늘의 알고는 여기까지...
728x90
반응형
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 9328 열쇠 (0) | 2019.09.19 |
|---|---|
| 백준 6087 레이저 통신 (0) | 2019.09.19 |
| 백준 9019 DSLR (0) | 2019.09.17 |
| 백준 2638 치즈 (0) | 2019.09.17 |
| 백준 1726 로봇 (0) | 2019.09.17 |
댓글