백준 7576: 토마토

문제 요약

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

BFS로 풀면 된다. 입력 받을 때 1을 입력 받은 위치를 모두 큐에 넣고 visited를 true로 바꾼 뒤, bfs하면 된다.

모든 토마토가 익었는가/익지 않았는가는 cnt라는 변수를 이용하여 익지 않은 토마토의 개수(0의 개수)를 세고, bfs하여 탐색한 횟수를 1씩 차감한다.

모두 끝났을 때 cnt가 0이면, 즉 익지않은 토마토의 개수와 bfs한 횟수가 동일할 경우 모든 토마토를 순회했다고 판단하여 답을 출력하면 되고, 그렇지 않은 경우에는 -1을 출력하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

queue<pair<short, short>> q;
bool visited[1000][1000];
int ary[1000][1000];
const short dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };

int main()
{
	int n, m, level = -1, cnt = 0, qsize;
	short f, s, nextF, nextS;
	cin >> m >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &ary[i][j]);
			if (ary[i][j] == 1) {
				q.push({ i,j });
				visited[i][j] = true;
			}
			else if (ary[i][j] == 0) cnt++;
		}
	}
	while (!q.empty()) {
		level++;
		qsize = q.size();
		while (qsize--) {
			f = q.front().first;
			s = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				nextF = f + dir[i][0];
				nextS = s + dir[i][1];
				if (nextF >= 0 && nextF < n && nextS >= 0 && nextS < m) {
					if (ary[nextF][nextS] == 0 && !visited[nextF][nextS]) {	
						cnt--;
						q.push({ nextF,nextS });
						visited[nextF][nextS] = true;
					}
				}
			}
		}
	}
	if (cnt == 0) printf("%d", level);
	else printf("-1");
	return 0;
}