[백준/BOJ] 7576번 토마토 (C++)

www.acmicpc.net/problem/7576

7576번: 토마토

BFS 유형의 문제입니다.

토마토가 있는 위치를 벡터에 담아서 큐에 넣어줬습니다. 큐가 진행되면서 visit 배열에 최소 일수가 기록됩니다. 예외처리만 제대로 해준다면 어렵지 않은 문제였습니다.

 

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

int m, n;
int map[1001][1001];
int visit[1001][1001];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pair<int, int > > v;

int BFS() {
	queue<pair<int, int > > q;
	for(int i = 0; i < v.size(); i++) {
		q.push(v[i]);
		visit[v[i].first][v[i].second] = 0;
	}
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if(visit[nx][ny] == -1 && map[nx][ny] == 0) {
					q.push( {nx, ny} );
					visit[nx][ny] = visit[x][y] + 1;
				}
			}
		}
	}
	
	int maxx = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(map[i][j] == 0 && visit[i][j] == -1) return -1;
			maxx = max(maxx, visit[i][j]);
		}
	}
	return maxx;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(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) {
    			v.push_back( {i, j} );
			}
		}
	}
	
	memset(visit, -1, sizeof(visit));
    cout << BFS();
}