문제 링크:https://www.acmicpc.net/problem/7576
<문제 풀이> BFS
이문제는 기본적인 bfs를 사용해서 최단거리를 구하면 됩니다.
그런데 익은 토마토가 여러 개이면 모든 익은 토마토에 대해서 동시에 출발을 해야 됩니다.
시작점을 여러개 두고 bfs를 동시에 진행하는 방법은
시작점을 모두 queue에 넣고 시작하면 됩니다. (그러면 번갈아가면서 push, pop을 하기 때문에 동시에 출발시킨 효과)
<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
|
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
using namespace std;
#define X first
#define Y second
int box[1000][1000];
int visited[1000][1000];
int dx[4] = {1 ,0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int n, m;
void bfs() {
queue<pair<int, int> > Q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (box[i][j] == 1) {
Q.push({ i,j });
}
if (box[i][j] == 0) {
visited[i][j] = -1;
}
}
}
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] >= 0) continue;
Q.push({ nx, ny });
visited[nx][ny] = visited[cur.X][cur.Y] + 1;
}
}
}
int cal_res() {
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] == -1) return -1;
res = max(res, visited[i][j]);
}
}
return res;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> box[i][j];
}
}
bfs();
cout << cal_res();
return 0;
}
|
cs |
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 10026번] 적록색약 (0) | 2021.11.05 |
---|---|
[백준 4179번] 불! (0) | 2021.11.04 |
[백준 4949번] 균형잡힌 세상 (0) | 2021.11.01 |
[백준 5430번] AC (0) | 2021.10.28 |
[백준 2164번] 카드2 (0) | 2021.10.27 |