문제
https://www.acmicpc.net/problem/7576
문제 요약
N × M 크기의 상자에 들어있는 토마토 정보가 주어진다.
1 : 익은 토마토가 있는 칸
0 : 익지 않은 토마토가 있는 칸
-1: 토마토가 들어있지 않은 칸
토마토를 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익게 된다.
+ 대각선은 인접하지 않다고 가정한다.
며칠이 지나면 토마토들이 모두 익는지 최소 일수를 출력한다.
저장될 때부터 모든 토마토가 익은 상태라면 0, 토마토가 모두 익지 못하는 상황이라면 -1을 출력한다.
코드
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#define MAX 1000
using namespace std;
int box[MAX + 1][MAX + 1];
bool visited[MAX + 1][MAX + 1];
int n, m, res;
queue<tuple<int, int>> q;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
void bfs() {
while (!q.empty()) {
int x, y;
tie(x, y) = q.front();
q.pop();
// 인접한 칸 탐색
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
// 이미 방문 했을 경우
if (visited[nx][ny]) continue;
// 토마토가 있지 않을 경우
if (box[nx][ny] == -1) continue;
// 상자 범위를 벗어난 경우
if (0 > nx || nx >= n || 0 > ny || ny >= m) continue;
visited[nx][ny] = true;
q.push({ nx, ny });
// 해당 칸이 익는데 걸리는 일수
box[nx][ny] = box[x][y] + 1;
}
}
}
int main() {
cin >> m >> n;
bool all = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> box[i][j];
if (box[i][j] != 1) {
all = false;
}
// 익은 토마토의 좌표를 큐에 저장
else {
q.push({ i, j });
visited[i][j] = true;
}
}
}
// 입력 받은 모든 토마토가 익은 경우
if (all) {
cout << 0;
return 0;
}
// bfs 탐색
bfs();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 탐색 종료에도 익지 않은 토마토가 있는 경우
if (box[i][j] == 0) {
cout << -1;
return 0;
}
// 토마토가 모두 익는 데에 걸리는 일수
res = max(box[i][j], res);
}
}
cout << res - 1;
}
코드 설명
1. 상자에 들어있는 토마토 정보를 입력 받는다.
1 - 1. 입력 받은 토마토가 모두 익었는지 체크한다.
1 - 2. 익은 토마토의 칸 정보를 BFS 탐색을 위해 큐에 저장한다.
2. BFS 탐색을 진행한다.
2 - 1. 초기 큐에 저장된 익은 토마토 칸부터 BFS 탐색을 통해 방문 가능한 칸을 모두 방문한다.
2 - 2. box[nx][ny]에는 (nx, ny) 칸에 익지 않은 토마토가 익을 때까지 걸리는 일수를 저장한다.
이전 방문 칸에 있는 (인접한) 토마토가 익을 때까지 걸리는 일수 + 1
=> box[nx][ny] = box[x][y] + 1
3. 탐색 종료 후에도 익지 않은 토마토가 존재하는지 체크하고, 토마토가 모두 익는 데 걸리는 일수를 출력한다.
토마토가 모두 익는데 걸리는 일수 = 탐색 종료 후 box배열에 저장된 일수 중 가장 큰 수 - 1
고찰
DFS를 좋아해서, DFS 문제만 풀다가 오랜만에 BFS로 풀었더니 조금 헤멨다..
알고리즘 문제 특성 상 BFS가 더 유리하기 때문에, BFS도 많이 연습하자.
'Algorithm Problems > 그래프' 카테고리의 다른 글
[백준/C++] 2206번: 벽 부수고 이동하기 (0) | 2024.07.14 |
---|---|
[백준/C++] 2252번: 줄 세우기 (1) | 2024.07.11 |
[백준/C++] 13565번: 침투 (0) | 2024.05.05 |
[백준/C++] 16562번: 친구비 (0) | 2024.04.16 |
[백준/C++] 16953번: A -> B (0) | 2024.03.09 |