[백준 BOJ][C++]7576번 토마토 풀이: BFS/DFS

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

7576번: 토마토

 

 이 문제는 BFS를 사용하여 해결할 수 있습니다. 

 

 M*N 크기의 토마토 농장에서 모든 토마토가 익을 때까지 걸리는 최소일은 익은 토마토로부터 시작해 그래프 탐색이 완료 되었을 때의 리프 노드 중, 최대 부모 노드의 수가 됩니다. 

 

 예시로 다음과 같은 3*3 토마토 농장을 들겠습니다. 

0  0  0

 0  0  0 

0  0  1

index: x(col), y(row)	0	1	2
0	0	0	0
1	0	0	0
2	0	0	1

 

 이제 이 토마토 농장의 토마토 정보를 가지고 BFS를 하면 방문 순서는 다음과 같습니다. 

 

 

익은 토마토의 위치인 (2, 2)에서 시작해 BFS를 하여 완료된 모습입니다. 

 

이때 각 리프 노드인 (1, 0), (0, 0), (0, 2)의 부모 노드 수는 각각 3개, 4개, 2개가 됩니다. 

 

 최댓값인 4가 모든 토마토가 익을 때까지 걸리는 최소일수가 됩니다. 

 

 

typedef struct node {
	int x, y;  //위치
	int parent_num; //부모 노드 개수
}node;

queue<node> tomato;

 queue에 들어가는 자료구조로는 토마토의 위치 x, y와 부모 노드의 개수 parent_num이 사용됩니다. 

 

 토마토 정보를 입력받을 때 1이라면 queue<node> tomato에 push해줍니다. 이때 parent_num의 값은 0이 됩니다. 

 

 queue에 정보를 기록했으면 이제 기존 bfs 방식과 동일하게 진행하면 됩니다. 

 

 이때 인접한 익지 않은 토마토 노드를 queue에 push할 때 해당 노드의 parent_num은 부모 노드의 parent_num+1이 되겠지요!

 

bool all_visit() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0 && !visit[i][j])
				return false;
		}
	}
	return true;
}

 bfs()가 완료되면 all_visit() 함수를 호출하여 익지 않은 토마토가 모두 익었는지 체크해야 합니다. 이때 false를 return 받게 되면 결과는 -1로 해주어야겠지요!

 

 

전체 코드입니다. 

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdlib>

using namespace std;

int m, n;
int map[1001][1001];
bool visit[1001][1001] = { false, };
int day = 0;

int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };

typedef struct node {
	int x, y;
	int parent_num;
}node;

queue<node> tomato;

bool all_visit() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0 && !visit[i][j])
				return false;
		}
	}
	return true;
}

void bfs() {

	node curr;

	while (!tomato.empty()) {
		curr = tomato.front();
		tomato.pop();

		for (int i = 0; i < 4; i++) {
			int tx = curr.x + dx[i];
			int ty = curr.y + dy[i];

			if (tx < 0 || tx >= m || ty < 0 || ty >= n)
				continue;
			if (visit[ty][tx] || map[ty][tx] != 0)
				continue;

			visit[ty][tx] = true;

			node child;
			child.x = tx;
			child.y = ty;
			child.parent_num = curr.parent_num + 1;

			tomato.push(child);
		}

		day = max(day, curr.parent_num);
	}

}

int main(void) {

	ios::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 >> map[i][j];

			if (map[i][j] == 1) {
				tomato.push({ j, i, 0 });
			}
		}
	}

	bfs();

	if (!all_visit())
		day = -1;

	cout << day;

	return 0;
}