[기출 중] 백준 7576 토마토

[문제]

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

[풀이]

BFS를 이용해서 푸는 문제이다. 익은 토마토(box[i][j]==1)는 큐에 row, col 좌표를 넣어준다. 큐가 빌 때 까지, 큐를 pop하고 반복문을 돌려 pop한 row, col 행의 상, 하, 좌, 우를 검토한다. 범위 내에 존재하고, 익지 않은 토마토가 들어있으면 box 값을 원래 값+1로 갱신해준다. 이는 모든 토마토가 익을 때까지 걸리는 최소 일수를 계산하기 위함이다. 이제 익은 토마토이므로 다시 큐에 넣어주고 cnt 값을 감소시켜준다. cnt값은 처음 익지 않은 토마토의 개수이다. while문을 탈출한 후에도 cnt 값이 0이 아니라면 익지 않은 토마토가 존재하므로 -1을 return하고, 0이라면 모든 토마토가 익었으므로 익을 때까지 걸린 최소 일수인 마지막에 pop한 큐에 들어있던 값인 row, col에 해당하는 box[row][col]-1을 return한다.

 

[코드]

#include <iostream>
#include <queue>
using namespace std;
int n, m, cnt;
int row, col;
queue<pair<int, int>> q;
int c[4] = {1, -1, 0, 0};
int r[4] = {0, 0, 1, -1};

int solution(int** box){
	//bfs. 익은 토마토는 큐에 넣기.
	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			if(box[i][j]==1){
				q.push(make_pair(i, j));
			}
		}
	}
	while(!q.empty()){
		int nrow, ncol;
		row = q.front().first;
		col = q.front().second;
		q.pop();
		for(int i=0; i<4; i++){
			nrow = row + r[i];
			ncol = col + c[i];
			if(nrow<m && nrow>=0 && ncol<n && ncol>=0){
				if(box[nrow][ncol]==0){ 
					box[nrow][ncol] = box[row][col] + 1;
					q.push(make_pair(nrow, ncol));
					cnt--;
				}
			}		
		}
	}
	if(cnt == 0)
		return box[row][col]-1;
	else {
		return -1;
	}
}

int main() {
	cin >> n >> m;
	int** box = new int*[m];
	for(int i=0; i<m; i++){
		box[i] = new int[n];
	}
	
	int check = 0;
	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			cin >> box[i][j];
			if(box[i][j]!=1)
				check = 1;
			if(box[i][j]==0)
				cnt++;
		}
	}

	if(!check)
		cout << 0;
	else 
		cout << solution(box);

	return 0;
}