[BFS]01-백준 7576 토마토

** 백준 7576번 대표적인 BFS 기초 문제 **

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

7576번: 토마토

 

 

 

---

정답 코딩

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



int visit[1000][1000] = { 0, };		//칸 방문 여부 조사
int m, n;							//가로 세로
int arr[1000][1000];				//1:익은 토마토, 0:안 익은 토마토, -1:토마토 없는 칸
int day = 0;						//익을 수 있는 토마토가 모두 익을 수 있는 최소 일 수


int adj_check_x[4] = { -1,1,0,0 };	//영향받는 인접 칸 x축
int adj_check_y[4] = { 0,0,-1,1 };	//영향받는 인접 칸 y축



/*		bfs()		*/

int bfs() {
	queue <pair<int, int>> q;				//<m*n토마토 상자의 x,y축>
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 1) {			//초기 익은 토마토 확인
				q.push(make_pair(i, j));	//q에 삽입
				visit[i][j] = 1;			//방문 체크
			}
		}

	while (!q.empty()) {	// q에 남은 익힐 수 있는 남은 토마토들이 남아 있는 상태인지 
		int q_size = q.size();					//날짜 구분을 위한 q크기
		for (int i = 0; i < q_size; i++) {
			int sx = q.front().first;	
			int sy = q.front().second;
			q.pop();							
			for (int k = 0; k < 4; k++) {		// 인접 4면 조사

				//칸 크기 초과 여부 조사 
				if ((sx + adj_check_x[k]) < m && (sx + adj_check_x[k]) >= 0 && (sy + adj_check_y[k]) < n && (sy + adj_check_y[k]) >= 0) {

					//방문하지 않았고, 토마토가 익을 수 있는 상태이면
					if ((arr[sx + adj_check_x[k]][sy + adj_check_y[k]] == 0) && visit[sx + adj_check_x[k]][sy + adj_check_y[k]] == 0) {
						q.push(make_pair((sx + adj_check_x[k]), (sy + adj_check_y[k]))); // q에 삽입
						visit[sx + adj_check_x[k]][sy + adj_check_y[k]] = 1;			//방문 체크
						arr[sx + adj_check_x[k]][sy + adj_check_y[k]] = 1;				//익은 상태 변경
					}
				}
			}
		}


		day++;		// 하루 경과
	}
	return(day - 1);	// 마지막 값이 q에 남아있고 크기와 방문조사를 수행하지 않고 +1한 경우를 위해 하루 감소
}


void main() {

	cin>> m >> n;
	//scanf_s("%d %d", &m, &n);		// 상자 칸 수 입력

	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];
			//scanf_s("%d", &arr[i][j]);		// 토마토 상태 입력


	/*		bfs() 실행	*/

	cout << bfs();
	//printf("총 %d일 소요\n", bfs());		//최소 일수 출력

}

 

 

---

 

아주 전형적인 BFS문제로 SAMSUNG SW EXPERT ACADEMY에서 BFS와 Queue 강의를 듣고 바로 첫 문제로 풀어보았다.

이 문제에서 핵심은 최소 며칠 걸렸는지 파악하는 것과 BFS의 시작점이 다수라는 것 (시작 시 익은 토마토인 1의 값이 여러 개)인 점이다.

첫번째는 Queue의 값을 push하고 기존 값을 pop하기 전마다 (다른 넓이를 탐색할 때마다) Queue의 크기를 확인하여 크기만큼 반복문을 돌린 횟수를 count한다. 즉 인접 값들을 queue값에 새로 넣기 전에 하루씩 증가되는 개념이다. 이 부분이 매우 이해하기 힘들었던 것 같다.

두번째로는 시작점이 다수여도 무관하다는 것. 방문여부와 방문가능 여부에 대한 확인을 토마토가 배열된 순차적으로 진행하지  않기 때문이다.

 

추가적으로 백준 문제풀이에 제출하면 'c++ error: ‘>>’ should be ‘> >’ within a nested template argument list' 라는 에러를 확인할 수 있다.  queue를 pair로 선언할 때 > 띄고 >로 써야되는데 이유는 모르겠다.
또한 main문에서 void main()으로 주면 에러나서 대신, int로 정의해서 return 값을 0을 주었다.

 

출력 콘솔