반응형
문제 링크: https://www.acmicpc.net/problem/2636
2636번: 치즈
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓
www.acmicpc.net
<문제 풀이> BFS
X로 표시된 곳엔 치즈가 없으니깐 X로 표시된 곳 중 한 곳에서 공기가 출발한다고 생각하고 BFS를 돌리면서 공기와 치지를 접촉시켜 보면 됩니다.
1. 공기는 이미 방문했던 곳을 다시 방문할 필요가 없다
2. 공기가 접촉한 적이 없는 치즈를 만나면 그곳을 한 시간 후 녹을 치즈로 바꾸고('c') 방문 체크를 합니다.
-> 그리고 한 시간 후 공기는 이 위치에서 다시 BFS를 진행하도록 임시 큐에 해당 좌표를 넣습니다.
-> 치즈가 녹으면 결국 그곳엔 공기가 생김
<C++ 소스 코드>
|
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
|
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
#define X first
#define Y second
int dx[4] = {0, -1, 0, 1}; //0 == right, 1 == up, 2 == left, 3 == down
int dy[4] = {1, 0, -1, 0};
int n, m;
int cheeze[100][100];
bool visited[100][100];
void AirBFS() {
queue<pair<int, int> > Q;
Q.push({ 0, 0 });
visited[0][0] = true;
int time = 0; // 걸린 시간
int last_cnt = 0; //마지막 녹기 한 시간 전에 남아있는 치즈 조각의 수
while (true) {
queue<pair<int, int> > temp;
bool flag = false; //한 시간 후 녹일 치즈가 있다면 true
int cnt = 0; // 한 시간 후 녹일 치즈의 개수
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (visited[nx][ny] || cheeze[nx][ny] == 'c') continue; // 이미 방문했거나 치즈가 공기에 접촉했으면 무시
if (cheeze[nx][ny] == 1) { // 공기에 접촉하지 않은 치즈이면
flag = true;
cheeze[nx][ny] = 'c'; // 한 시간 후 치즈를 녹인다.
cnt++; // 한 시간 후 녹일 치즈의 개수 증가
temp.push({ nx, ny }); // 공기는 한 시간 후 녹을 치즈의 위치에서 다시 시작
visited[nx][ny] = true;
}
else { // 빈 공간이면 그냥 이동
Q.push({ nx, ny });
visited[nx][ny] = true;
}
}
}
if (!flag) { //한 시간 후 녹일 치즈가 없다면
cout << time << '\n' << last_cnt;
break;
}
last_cnt = cnt; //가장 최근에 녹인 치즈의 개수
time++; // 한 시간 뒤
Q = temp;
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> cheeze[i][j];
}
}
AirBFS();
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 12100번] 2048(Easy) (0) | 2022.01.05 |
|---|---|
| [백준 18808번] 스티커 붙이기 (0) | 2022.01.05 |
| [백준 15683번] 감시 (1) | 2022.01.04 |
| [백준 1987번] 알파벳 (0) | 2022.01.03 |
| [백준 18809번] Gaaaaaaaaaarden (0) | 2022.01.02 |
