본문 바로가기

Algorithm Problems/그래프

[백준/C++] 7576번: 토마토

문제

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도 많이 연습하자.