백준 7576 토마토(c++)

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

7576번: 토마토

<코드>

#include <iostream>
#include <queue>
#include <algorithm>
#define max 1001
using namespace std;
int n,m;
int tomato[max][max];
queue<pair<int,int>>q;
bool visited[max][max];
int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
void bfs()
{
	visited[max][max] = {false};
	while(!q.empty()){
		pair<int,int> cur = q.front();
		q.pop();
		visited[cur.first][cur.second] = true;
		for(int i=0;i<4;i++)
		{
			int sr = cur.first + mov[i][0];
			int sc = cur.second + mov[i][1];
			if(sr>=0 && sc>=0 && sr<n && sc<m && !visited[sr][sc] && tomato[sr][sc]==0)
			{
				visited[sr][sc] = true;
				q.push({sr,sc});
				tomato[sr][sc] = tomato[cur.first][cur.second] +1;
			}
				
	}
}
}

int main()
{
	cin>>m>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++){
			cin>>tomato[i][j];
			if(tomato[i][j]==1){
				q.push({i,j});
			}
		}	
	}
	bfs();
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++){
			if(tomato[i][j]==0 && !visited[i][j]){
				cout<<-1<<'\n';
				return 0;
			}
			if(ans<tomato[i][j]){
				ans = tomato[i][j];
			}
		}	
	}		
	cout<<ans-1<<'\n';
}

<풀이과정>

이 문제는 기본적인 bfs 문제이다. 

-1 : 토마토가 존재하지 않는 부분 0 : 토마토가 익지 않는 부분 1 : 토마토가 익은 부분

우선적으로 큐에 토마토가 익은 부분의 좌표들을 넣어준다.(시작점의 좌표가 여러 개 일수도 있음) 그리고 익은 좌표를 상하좌우 이동시키고(토마토가 익은 부분은 익지 않은 부분에 상하좌우로 영향을 끼치기 때문이다) 토마토가 익지 않은 부분이 있으면, 

상하좌우로 이동한 값 = 이전의 좌표값 + 1로 만들어준다. 

6 4
// 입력
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1
//출력

다음 입출력을 보면 토마토가 익은 좌표값은 (0,0) , (5,4) 총 두개가 있는데, 각각 q에 넣고 bfs 함수를 호출하면,

1	-1	7	6	5	4
2	-1	6	5	4	3
3	4	5	6	-1	2
4	5	6	7	-1	1

이러한 형태(bfs)로 값이 바뀌게 된다(전형적인 bfs 알고리즘이다)

floodfill 알고리즘을 생각해보면 쉽게 알 수 있다. 자기 자신(토마토가 익은 부분)을 기준으로 값을 1씩 증가시켜주는 것이다. 마지막에 ans-1은 시작좌표가 1이기 때문에 -1을 해주었다. (기존 bfs는 시작 좌표가 0이다)