[BFS] 백준 7576 토마토

 

www.acmicpc.net/problem/7576

7576번: 토마토

수행기간 : 2021/01/26~ 01/28

정말 오래걸린 문제였다. 이 문제를 거의 3일에 걸쳐서 잡고 있었는데, 그만큼 스트레스도 많았고.. 힘들었다. 분명 2~3시간 내로 풀릴 것만 같았던 문제는 수 많은 오류들과 함께 3일이라는 시간이 걸렸다. bfs를 써서 풀었고, cnt를 조정하기가 힘들었다.

 

 

 

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

int map[1001][1001];
//vector<vector<int>> map;
int m, n;//가로세로
int cnt = 0;
int dx[4] = { -1,1,0,0, };
int dy[4] = { 0,0,-1,1 };
queue<pair<int, int>> q;

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

int main() {
	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));
			}
		}
	}
	bfs();
	for (int i = 0; i < n;i++) {
		for (int j = 0;j < m;j++) {
			if (map[i][j] == 0) {
				cout << "-1";
				return 0;
			}
			if (cnt < map[i][j]) {
				cnt = map[i][j];
			}
		}
	}
	cout << cnt - 1;
}