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

 

1) 문제설명

백준 Online Judge 7576번 토마토

백준 Online Judge 7576번 토마토

 

2) 아이디어

1. BFS의 시작점이 여러 곳이다

2. 전개가 막혀있는 부분이 있다.

3. 전개가 막혀서 0(익지 않은 토마토)을 1(익은 토마토)로 바꾸지 못할 경우 -1을 출력한다.

정도만 해결한다면 기본 BFS문제와 다른 점이 없다.

1번의 경우 시작점을 미리 큐에 넣어둠으로써 해결하였고 2번의 경우 if문으로 예외 처리하였다. 3번의 경우는 BFS를 사용해서 0 (익지않은 토마토)을 1 (익은 토마토)로 교체해 준다음에 배열 처음부터 끝까지 순회하면서 0이 있다면 -1을 출력하는 것으로 해결하였다.

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

int arr[1001][1001];
int range[1001][1001];
int m, n;
int result;
queue<pair<int, int>> q;
void bfs(int x, int y) {
	
	
	
	while (!q.empty()) {

		x = q.front().first;
		y = q.front().second;

		q.pop();
		int dx[] = { -1,1,0,0 };
		int dy[] = { 0,0,-1,1 };

		for (int i = 0; i < 4; i++) {
			int nx, ny;
			nx = x + dx[i]; // 6 
			ny = y + dy[i]; // 4
			if (nx < 1 || ny < 1 || nx > n || ny > m || arr[nx][ny] == 1) { // 범위에서 벗어나거나 이미 익은 토마토는 넘어간다.
				continue;
			}
			else { // 썩은 토마토 or 익지않은 토마토일때
				
				if (arr[nx][ny] == 0) { // 익지않은 토마토일때
					arr[nx][ny] = 1; // 익었다고 표시
					q.push(make_pair(nx, ny)); // 큐에 삽입
					range[nx][ny] = range[x][y] + 1; // 최소일수 카운트
					result = range[nx][ny];
				}
			}
		}
	}
}

int main() {
	
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				q.push(make_pair(i, j)); // 큐에 미리 넣어놔
			}
		}
	}
	bfs(1, 1);
	
	for (int i = 1; i <= n; i++) { // 처음부터 끝까지 탐색해서
		for (int j = 1; j <= m; j++) {
			if (arr[i][j] == 0) { // 0이 존재한다면
				result = -1; // 결과값을 -1로 한다
			}
		}
	}
	cout << result << endl;
}