[백준] 알고리즘 7576번 - 토마토문제

문제

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

7576번: 토마토

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
#include <stdio.h>
using namespace std;
int n, m, cnt;
int arr[1001][1001];
int dist[1001][1001];
bool check[1001][1001];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
queue<pair<int, int>> qu;
void bfs() { 
	while (!qu.empty()) {
		int ox = qu.front().first;
		int oy = qu.front().second;
		qu.pop();
		for (int i = 0; i < 4; i++) {
			int nx = ox + dx[i];
			int ny = oy + dy[i];
			if (nx<0 || nx>n - 1 || ny<0 || ny>m - 1) continue;
			 
			if (arr[nx][ny] == 0 && !check[nx][ny]) {
				check[nx][ny] = true;
				qu.push({ nx,ny });
				dist[nx][ny] = dist[ox][oy] + 1;
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	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) {
				qu.push({ i,j });
				dist[i][j] = 1;
			}
			else if (arr[i][j] == -1) {
				dist[i][j] = -1;
			}
		}
	}
	bfs(); 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (dist[i][j] == 0)
			{
				cout << "-1";
				return 0;
			}
			if (cnt < dist[i][j]) cnt = dist[i][j];
		}
	}
	cout << cnt - 1;
}

해설

 

문제에서 토마토가 있으면 인접한 토마토는 익는다고한다. 그렇다면 bfs를 통해서 자기가 갈 수 있는 곳은 토마토를 익혀줘야한다. 문제에서 특이한점은 처음 주어진 토마토가 정해진 위치가 아니라 여러군데 있을 수 있는점이다. 이건 어떻게 해결해볼까..

배열에 토마토정보를 입력받을때 1이면 바로 큐에 넣어준다. 그렇다면 처음에 1이 여러개 있어도 첫번째 1이 갈 수 있는 공간을 bfs로 탐색하여 다른 0인 토마토들을 익혀줬다면, 그다음에 큐에들어간1이(처음 박은1) 또 탐색을시작한다. 그렇다면 자연스럽게 중앙이든 어디든 만나게되며 종료하게된다.

이게 바로 문제의 핵심인 것 같다.