[99클럽/코딩테스트 챌린지/C++] 토마토 익히기 문제 해결을 통한 BFS 활용법 학습

이 문제는 여러 겹의 상자 안에 보관된 토마토가 익는 과정을 모델링하는 문제다. 상자 안에는 익은 토마토, 익지 않은 토마토, 그리고 토마토가 들어있지 않은 칸이 있다. 하루가 지나면 익은 토마토는 인접한 여섯 방향(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)에 있는 익지 않은 토마토를 익게 만든다. 이 문제는 모든 토마토가 익을 때까지 최소 며칠이 걸리는지, 혹은 익지 못하는 토마토가 남는지를 계산하는 프로그램을 작성하는 것이다.

문제 링크 : 

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

접근법

익은 토마토가 동시에 여러 방향으로 퍼져 나가는 상황을 모델링하기 위해 BFS(너비 우선 탐색)를 사용한다. 모든 익은 토마토의 위치를 큐에 넣고 BFS를 수행하여 익은 토마토가 하루 단위로 주변에 영향을 미치도록 한다. BFS를 통해 하루 단위로 퍼져나가는 과정을 통해 전체 익는 기간을 계산하고, 최종적으로 익지 않은 토마토가 남아 있는지를 확인하여 모든 토마토가 익는지 판단한다.

 

코드 풀이 

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <math.h>
#include <map>
#include <queue>
using namespace std;
const int GOOD = 1;
const int NONE = 0;
const int EMPTY = -1;
// 위, 오른쪽 , 왼쪽, 앞 , 뒤, 아래 
int dy[6] = { 1,0,0,0,0,-1 };
int dx[6] = { 0,1,-1,0,0,0 };
int dz[6] = { 0,0,0,1,-1,0 };

int X,Z,Y;
int Total = 0;
int maps[105][105][105];
int visited[105][105][105];
queue<tuple<int, int, int>> q;
void ClearVisited() {
	for (int y = 0; y < 105; y++) {
		for (int z = 0; z < 105; z++) {
			for (int x = 0; x < 105; x++) {
				visited[y][z][x] = 0;
			}
		}
	}
}

bool findNone() {
	for (int y = 0; y < Y; y++) {
		for (int z = 0; z < Z; z++) {
			for (int x = 0; x < X; x++) {
				if (maps[y][z][x] == NONE) {
					return true;
				}
			}
		}
	}
	return false;
}

int bfs() {

	int maxValue = 0;
	while (!q.empty())
	{
		auto current = q.front();
		q.pop();

		int currentY = get<0>(current);
		int currentZ = get<1>(current);
		int currentX = get<2>(current);
		visited[currentY][currentZ][currentX] = 1;

		for (int i = 0; i < 6; i++) {
			int newY = dy[i] + currentY;
			int newZ = dz[i] + currentZ;
			int newX = dx[i] + currentX;
			if (newY < 0 || newZ < 0 || newX < 0 || newY >= Y || newZ >= Z || newX >= X)
				continue;
			if (visited[newY][newZ][newX]) continue;
			if (maps[newY][newZ][newX] == EMPTY) continue;
			if (maps[newY][newZ][newX] == NONE) {
				maps[newY][newZ][newX] = maps[currentY][currentZ][currentX] + 1;
				maxValue = max(maps[newY][newZ][newX], maxValue);
				visited[newY][newZ][newX] = 1;
				q.push({ newY,newZ,newX });
			}
		}
	}

	return maxValue - 1;
}

int main() {

	cin >> X >> Z >> Y;

	int noneCount = 0;
	for (int y = 0; y < Y; y++) {
		for (int z = 0; z < Z; z++) {
			for (int x = 0; x < X; x++) {
				std::cin >> maps[y][z][x];
				if (maps[y][z][x] == GOOD) {
					q.push({ y,z,x });
				}
				if (maps[y][z][x] == NONE) {
					noneCount++;
				}
			}
		}
	}
	if (noneCount == 0) {
		std::cout << noneCount << '\n';
		return 0;
	}
	
	int day = bfs();
	if (findNone()) {
		std::cout << -1 << std::endl;
	}
	else
	{
		std::cout << day << std::endl;
	}


	return 0;
}

코드 설명

1, 상수와 방향 배열 정의: 상자 안에서의 토마토 상태를 나타내는 상수를 정의하고, 여섯 방향으로 탐색하기 위해 방향 배열 dy, dx, dz를 설정한다.

 

2, 입력 처리 및 초기화:

• 상자의 크기 X, Z, Y를 입력받고, 3차원 배열 maps에 토마토 상태를 저장한다.
• 익은 토마토의 위치는 GOOD으로 표시하고, 큐에 익은 토마토의 좌표를 저장한다.
• 익지 않은 토마토 개수를 noneCount로 세어 초기 상태에서 모든 토마토가 익은 상태라면 프로그램을 종료한다.

3, BFS 수행: bfs() 함수에서 BFS를 사용하여 익은 토마토가 하루 단위로 익지 않은 토마토에 퍼지도록 한다.

• 큐에서 현재 위치를 꺼내고, 인접한 여섯 방향을 탐색하여 익지 않은 토마토(NONE)가 있으면 익게 (GOOD) 변경하고 maps 배열에서 해당 위치에 걸린 일수를 저장한다.
• maxValue에 현재까지의 최대 일수를 저장하여 모든 토마토가 익는 데 걸린 총 일수를 추적한다.

4, 익지 않은 토마토 여부 확인: findNone() 함수는 BFS가 끝난 후에도 익지 않은 토마토가 남아 있는지 확인하는 역할을 한다. 만약 익지 않은 토마토가 남아 있다면 -1을 출력하고, 그렇지 않으면 day 값을 출력한다.

 

배운 점

1, BFS의 동시적 전파 특성: BFS는 여러 시작 지점에서 동시에 퍼져 나가는 상황에 적합한 알고리즘이다. 이를 통해 하루 단위로 여러 방향에서 동시에 전파되는 토마토 익힘 과정을 쉽게 모델링할 수 있었다.

 

2, 상태 점검과 예외 처리: 문제에서 모든 토마토가 익을 수 없는 경우에 대한 예외 처리와, 처음부터 모든 토마토가 익어 있는 경우를 빠르게 확인하는 방식이 중요하다.

 

3, 큐를 이용한 효율적 탐색: BFS에서 익은 토마토들을 큐에 넣고 동시에 전파를 처리하여 효율적으로 탐색을 수행하는 방법을 배웠다.

결론

이 문제를 통해 BFS를 사용하여 여러 방향에서 동시에 전파되는 문제를 해결할 수 있는 능력을 익혔다. 또한 상태 점검과 예외 처리가 프로그램의 정확성과 효율성을 높이는 데 필수적이라는 것을 알게 되었다.