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

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

 

문제 설명

n X m의 배열이 주어졌을 때, 토마토가 언제쯤 다 익을지 계산하는 문제이다. 

익은 토마토는 상하좌우로 영향을 주기에 하루가 지나면 상하좌우에 있는 익지 않은 토마토가 익는다.

토마토가 며칠이 지나면 모두 다 익는지, 그 최소 일수를 구하는 문제이다.

 

주요 로직

1. 최소 일수를 구하기 때문에 bfs로 풀어야한다.

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n,m;
vector<pair<int,int>> v;
int arr[1004][1004], visited[1004][1004];
int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.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) v.push_back({i,j});
		}
	}
	
	queue<pair<int,int>> q;
	for(auto it : v){
		visited[it.first][it.second] = 1;
		q.push({it.first, it.second});
	}
	
	while(q.size()){
		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] || arr[ny][nx] == -1) continue;
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ny,nx});
		}
	}
	
	int ret = 0;
	bool flag = true;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(visited[i][j] == 0 && arr[i][j] != -1) flag = false;
			ret = max(ret, visited[i][j]);
		}
	}
	
	if(flag) cout << ret-1 << "\n";
	else cout << "-1\n";
	
	return 0;
}