BFS 및 DFS - 백준 7576번 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

IDEA

토마토가 다 익는데 걸리는 최소시간을 구하는 문제다 . 최소시간이라 BFS를 사용했다. 

이전에 풀었던 문제들과 마찬가지로 최소시간,최소비용 등이라서 VISITED를 따로 쓰지않고 맵 자체를 거리로 업데이트해줬다. 

 

1. 맨 처음부터 모두 다 익어있다면 0을 출력해야한다. -> 맨 처음 입력받으면서 익지않은 토마토 즉 0의 개수를 센다.

0의 개수가 0이라면 맨 처음부터 모두 익어있다는 뜻이므로 0을 출력한다.

 

2. 입력받으면서 현재 토마토가 있는 좌표 즉, map 값이 1인 좌표들을 큐에 넣는다. 

 

3. bfs를 실행한다.

큐의 front를 꺼내 front 좌표의 사방 좌표가 익을 수 있는 지 확인한다.

사방 좌표가 범위내에 있으면서 0이라면 익혀준다. 익는데는 하루가 걸리므로 이전 토마토가 익는데 걸린 시간 + 1만큼 필요하다 . map[nx][ny] = map [x][y] + 1 로 익는 날짜를 표시해준다. 

이후 max_day를 통해서 현재 토마토가 익기까지 며칠이 걸리는지 파악한다. 

원래 토마토는 이미 익어있기때문에 0부터 시작해야되는데 토마토의 값이 1이므로 max_day -1 이 진짜 소요시간이다.

 

4. check함수를 실행한다. 

2중 for문을 돌며 0이 있는지 확인한다. 0이 존재한다는 뜻은 모두 익지 못했단 뜻이다. 이때 -1을 반환해준다. 

만일 0이 없다면 모두 다 익었다는 뜻이므로 max_day를 반환해준다. 

 

CODE

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

int n, m;
int map[1000][1000];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };

queue<pair<int,int>>tomato;
int check(int max_day) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0) cnt++;
		}
	}
	if (cnt == 0) return max_day;
	else return -1;
}

int bfs() {
	int max_day = 0;
	while (!tomato.empty()) {
		int x = tomato.front().first;
		int y = tomato.front().second;
		tomato.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (-1 < nx && nx < n && -1 < ny && ny < m && !map[nx][ny]) {
				map[nx][ny] = map[x][y] + 1;
				max_day = max(max_day, map[nx][ny]);
				tomato.push({ nx,ny });
			}
		}
	}
	return max_day - 1;
}

int main() {
	scanf("%d %d", &m, &n);
	int zero_cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1) tomato.push({ i,j });
			if (map[i][j] == 0) zero_cnt++;
		}
	}

	if (zero_cnt == 0) printf("0\n");
	else printf("%d\n" , check(bfs()));
}