[백준 / C++] 7576번 토마토 - (1) , BFS

백준 7576번 토마토

 

---

토마토 문제풀이

토마토 문제는 하루 동안 상, 하, 좌, 우에 있는 토마토들이 익게 되는데 며칠만에 익게 되는지 최소 값을 찾는 문제이다.

상,하,좌,우 + 최소값을 얘기할 때 BFS를 자연스레 떠올리게 되었다.

 

- 토마토 창고 크기는 M * N 

- M * N 크기의 창고에서 토마토의 각 상태 (1 : 익음, 0 : 안 익음, -1 : 존재 X) 를 저장한다. 만약 토마토가 익은 상태 (1) 이면 queue에 저장

- queue에 저장된 값 중 front에 있는 값을 빼와서, 그 값의 상, 하, 좌, 우를 탐색한다. 탐색 조건으로는 0부터 m과 n 사이에 있어야하며, 상태가 0이여야 한다. 

- 만약 BFS를 다 돌고 나서, 0이 존재한다면 -1로 둘러쌓여있어서 탐색할 수 없다는 표시로 -1을 출력하고 종료한다.

 

---

또한, 최소거리를 찾기 위해서는 현재 위치에서 다음 탐색하는 위치를 + 1 해주는게 이상적인 접근이다.

아래 다른 블로그 글의 사진을 참고하면 좋을 것 같다. 출처는 밑에 링크이다.

https://jdselectron.tistory.com/55

 

이렇게 하면 마지막에 거리 중 제일 큰 것을 탐색하여, 주어진 값을 출력하면 끝이다. 

---

토마토 메인 코드

#include <iostream>
#include <queue>
using namespace std;

int tomato[1000][1000];
bool check[1000][1000];

queue<pair<int,int>> que;

int dx[4] = { -1, 0 , 1, 0 };
int dy[4] = { 0 , 1 , 0 , -1 };

int main() {
	int n, m;
	cin >> m >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> tomato[i][j]; 
			if (tomato[i][j] == 1) {
				que.push({ i,j });
			}
		}
	}

	while (!que.empty()) {
		pair<int, int> num = que.front();
		que.pop();
		//cout << num.first << " " << num.second << '\n';
		//check[num.first][num.second] = 1;

		for (int i = 0; i < 4; i++) {
			int X = num.second + dx[i];
			int Y = num.first + dy[i];

			if (X < m && Y < n && X >=0 && Y >=0) {
				if (tomato[Y][X] == 0 && check[Y][X] == 0) {
					que.push({ Y,X });
					tomato[Y][X] = tomato[num.first][num.second] + 1;
					check[Y][X] = 1;
					//cout << " X , Y : " << Y << " " << X << '\n';

				}

			}
		}
		
	}
	int max = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (tomato[i][j] > max) max = tomato[i][j];
			if (tomato[i][j] == 0) {
				cout << -1;
				return 0;
			}
		}
	}

	cout << max-1;
	
	return 0;
}