PS/깊이 우선 탐색, 너비 우선 탐색[DFS, BFS]

백준 7576 토마토(c++)

SeungbeomKim 2022. 8. 14. 19:57

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

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

<코드>

#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이다) 

'PS > 깊이 우선 탐색, 너비 우선 탐색[DFS, BFS]' 카테고리의 다른 글

백준 2644 촌수계산(c++)  (0) 2022.08.15
백준 1697 숨바꼭질(c++)  (0) 2022.08.14
17086 아기 상어 2(c++)  (0) 2022.08.12
백준 1260 DFS와 BFS(c++)  (0) 2022.08.12
백준 14502 연구소(c++)  (0) 2022.08.09