[백준 7576] 토마토 (BFS) (C++)

문제 출처

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

7576번: 토마토

구현 방법

1. 이차원 배열 형태의 input이 주어지고, 문제를 읽어보았을 때, DFS나 BFS와 같은 그래프 순회 알고리즘을 사용해야 한다는 것을 직관적으로 알 수 있다.

 

2. DFS를 사용할지, BFS를 사용할지 선택을 해야 한다.

   -> 단순히 시작점부터 도착점까지 그래프를 순회하는 유형의 문제에서는 DFS를 사용하든 BFS를 사용하든 상관 X

        (최단 거리가 보장되어야 한다면 BFS를 사용해야 한다.)

   -> 그러나, 이 문제에서는 무조건 BFS를 사용해야 한다!!

   -> 익은 토마토가 들어있는 칸(이차원 배열에서 1의 값을 갖는 칸)으로부터, 인접해 있으면서 익지 않은 토마토가 들어있는 칸(이차원 배열에서 0의 값을 갖는 칸)에 접근할 때 이 칸들은 동일한 날짜 정보를 가져야 하기 때문이다.

   -> DFS를 사용하게 되면, 가능한 한 계속 일방적으로 깊숙이 탐색을 하기 때문에, 어떠한 칸의 인접한 칸들에 동일한 날짜 정보가 저장된다고 보장할 수 없다.

 

3. 기존의 BFS 함수 형태에서 약간의 변형이 필요하다.

   -> 이 문제에서 가장 주의해야 할 점은 처음에 주어지는 익은 토마토의 개수가 여러 개일 수 있다는 점이다.

   -> 이 여러 개의 익은 토마토들은 날짜가 하루 지날 때마다 동시에 각자의 인접한 익지 않은 토마토들을 익게 만들어야 한다.

   -> 기존의 BFS 함수 형태로 구현한 다음에, main 함수에서 이중 for문을 통해 arr[i][j] == 1인 경우에 bfs(i, j) 형태로 코드를 작성하게 되면, arr[i][j] = 1인 칸들로부터 동시에 인접한 익지 않은 토마토에 접근하도록 구현하지 못하게 된다.

   -> 그래서, 처음에 이차원 배열 정보를 저장받을 때, arr[i][j] == 1인 경우에 queue에 이 {i, j}를 모두 push함과 동시에 visited[i][j] = 1로 설정해둔다.

   -> 그러면, 기존의 BFS 함수 내에서 맨 초기에 visited[y][x] = 1, q.push({y, x}) 코드를 작성하지 않아도 된다.

 

4. 처음에 익지 않은 토마토가 들어있는 칸 (i, j)에 대해서 visited[i][j] = 1로 설정해둔 채로 인접한 칸의 숫자를 증가시켰기 때문에, 마지막에 출력해야 할 결과는 res - 1이 되어야 한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;
int m, n;
int arr[1000][1000];
int visited[1000][1000];
queue <pair<int, int>> q;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };

void bfs() {
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= n || nx >= m)
				continue;
			if (visited[ny][nx] == 0 && arr[ny][nx] == 0) {
				visited[ny][nx] = visited[y][x] + 1;
				q.push({ ny, nx });
			}
		}
	}
}
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> m >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				q.push({ i, j });
				visited[i][j] = 1;
			}
				
		}
	bfs();
	int res = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0 && visited[i][j] == 0) {
				cout << -1;
				return 0;
			}
			if (res < visited[i][j])
				res = visited[i][j];
		}
	cout << res - 1;
	return 0;
}