백준 7576번 토마토 (BFS)

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

7576번: 토마토

BFS문제를 풀어보자.

이러한 맵 형식의 bfs 문제는 map, visited, dx, dy는 바로 전역변수로 선언하면 편하다.

 - map : 토마토 입력 변수

 - visited : 방문했는지 확인하는 변수

 - dx, dy : 상하좌우 이동할 변수

토마토가 모두 익을 때까지 최소 날짜를 출력해야 한다.

 

우선 input 값을 받을 때, 1에 해당하는 토마토 값을 모두 q에 넣는다.

실질적으로 while에 해당하는 부분이 bfs 구현부분이라고 보면 된다.

q가 비어 있을 때까지, q의 가장 앞에 있는 값을 현재 좌표(cx, cy)로 두고 q를 pop한다.

그리고 상하좌우를 탐색하기 위해 for문을 수행하는데, (nx, ny)값이 범위를 벗어나는 경우는 생략한다.

다음으로 방문하지 않았거나 (visited !=1), 다음으로 방문할 토마토 값이 0인 부분만 탐색한다.

방문표시를 하고, q에 삽입하고, map값을 현재 위치에서 +1 값을 더해준다.

그러면 이전 값에서 1씩 증가하므로 총 며칠이 걸렸는지 확인할 수 있다.

1부터 시작했으므로 빼기 1 한 값을 출력하고 만약 토마토 값이 0이 있으면 모두 익지 않은 것이므로 -1을 출력한다.

 

#include<iostream>
#include<queue>

using namespace std;

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

queue<pair<int, int>> q;

int main(void) {
	int m, n;
	int ans = 0;
	cin >> m >> n;

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

	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

			if (visited[nx][ny] != 1 && map[nx][ny] == 0) {
				visited[nx][ny] = 1;
				q.push(make_pair(nx, ny));				
				map[nx][ny] = map[cx][cy] + 1;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (ans < map[i][j]) {
				ans = map[i][j];
			}
			if (map[i][j] == 0) {
				cout << "-1\n";
				return 0;
			}
		}
	}

	cout << ans - 1 <<'\n';

	return 0;
}