[백준] 토마토 (BFS)

이번 문제는 BFS 알고리즘의 응용 문제로 최단 거리를 구하는 문제다. 여태까지 풀었던 최단 거리 문제와 달리 여러가지 상황이 있을 수 있는데 문제를 보며 확인해보자.

 

백준 7576번 토마토 문제

 

이 문제는 여러가지 입력 값이 필요하다. 많은 돌발 상황이 나오기 때문이다. 먼저 가장 일반적인 상황의 입력 값을 살펴보자.

 

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

 

이런 경우에는 인접 행렬에서 익은 토마토 (1) 를 검색해서 BFS로 최단 경로를 찾으면 된다.

 

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

 

이 경우에는 모든 토마토가 익을 수 없으므로 -1을 출력해야 한다. 일단 BFS로 탐색 후 인접 행렬에 0이 있는지 체크하면 된다.

 

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

 

익은 토마토가 시작점과 끝점 두 군대에 존재한다. 이 경우를 조심해야 한다. 여태까지 풀어왔던 문제들은 인접 행렬에서 1을 찾으면 그 좌표를 시작으로 탐색을 하는데, 이 경우에는 절대 원하는 답이 나오지 않는다. 이유는 시작점과 끝점 동시에 탐색을 시작할 수 있기 때문이다. 따라서 큐에 목적지를 추가하는 방법이 기존과는 달라야 한다. 밑에 코드에서 살펴보자.

 

2 2
1 -1
-1 1

 

익은 토마토가 모두 들어가 있는 경우는 찾기 쉽다. 최대 박스 용량이 익은 토마토의 갯수와 같으면 0을 출력하면 된다. 최대 박스 용량은 (M * N) - (막힌 부분 갯수) 로 구한다.

 

코드는 아래와 같다.

 

#include <stdio.h>
#define MAX 1000

typedef struct Queue {
	int x;
	int y;
	int size;
} Queue;

int front = -1, rear = -1;
Queue Q[MAX * MAX];

int Map[MAX][MAX];
int Visited[MAX][MAX];

int px[] = {-1, 1, 0, 0};
int py[] = {0, 0, -1, 1};

int BFS (int maxY, int maxX) {
	// 탐색 시작
	while (front < rear) {
		// 큐에서 꺼내기
		front++;
		
		int x = Q[front].x;
		int y = Q[front].y;
		int size = Q[front].size;
		
		// 왼, 오, 위, 아 체크
		for (int i = 0; i < 4; i++) {
			int nx = px[i] + x;
			int ny = py[i] + y;
			
			// 유효한 좌표인지 체크
			if (nx < 0 || nx >= maxX || ny < 0 || ny >= maxY) {
				continue;
			}
			
			// 체크하지 않았고, 익지 않았다면 체크 리스트에 추가
			if (Map[ny][nx] == 0 && !Visited[ny][nx]) {
				// 다음 탐색로에 등록
				rear++;
				Q[rear].x = nx;
				Q[rear].y = ny;
				Q[rear].size = size + 1;
				
				// 익은놈 체크
				Map[ny][nx] = 1;
				
				// 방문 표시
				Visited[ny][nx] = 1;
			}
		}
	}
	
	return Q[rear].size;
}

int main(void) {
	int N = 0, M = 0;
	int Empty = 0, Tomato = 0, maxCount = 0;
	
	scanf("%d %d", &M, &N);
	
	// 박스에 토마토 담기
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			int InputBox = -1;
			scanf("%d", &InputBox);
			
			// 빈 공간일 경우, Empty 카운터 + 1
			if (InputBox == -1) {
				Empty++;
			} else if (InputBox == 1) {
				Tomato++;
			}
			
			Map[y][x] = InputBox;
		}
	}
	
	// 박스의 최대 공간 - Empty와 모두 익은 토마토의 갯수가 같으면 1 출력하고 종료
	if ((M * N) - 1 == Tomato) {
		printf("0\n");
		return 0;
	}
	
	// 한쪽에만 익은 토마토가 있으라는 보장이 없다.
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			// 익은 토마토는 모두 큐에 넣는다.
			if (Map[y][x] == 1) {
				rear++;
				Q[rear].x = x;
				Q[rear].y = y;
				Q[rear].size = 0;
				
				// 방문 표시
				Visited[y][x] = 1;
			}
		}
	}
	
	// 탐색 시작
	maxCount = BFS(N, M);
	
	// 안익은 토마토가 있는지 확인
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			// 익은 토마토이고, 체크하지 않았다면 진행
			if (Map[y][x] == 0) {
				maxCount = -1;
				break;
			}
		}
	}
	
	printf("%d\n", maxCount);
	
	return 0;
}

 

큐에 좌표를 등록하는 부분이 BFS 함수 내부에 있지 않은 이유는, 박스를 최초에 확인할 때 익은 토마토가 한 개라는 가정이 없기 때문이다. 즉, 탐색이 동시다발적으로 일어나는 경우 최단 경로가 나오기 때문에 방문해야 할 좌표를 미리 등록하는 것이다. 이 상황을 인지해야만 이 문제를 풀 수 있다.