백준 7569_토마토(C++)

 

www.acmicpc.net/problem/7569

7569번: 토마토

[문제 풀이]

BFS를 이용하여 문제를 풀었습니다.

이 문제는 토마토가 아래, 위 옆으로 하루에 한 칸 씩 익어가며 며칠 만에 토마토가 모두 익을 수 있는가를 찾는 문제입니다. 조금 특이하게 3차원 배열을 이용하는 BFS 문제였습니다. 구현 방식은 기본적인 BFS 방식과 유사합니다. 다만 좌표의 옆만 보는 것이 아닌 아래위를 함께 봐야 하는 문제입니다.

 

코드 설명

• 배열을 입력받으며 토마토가 있는 1의 위치와 움직인 횟수 0을 큐에 넣어줍니다.
• 큐에 값이 없을 때까지 반복하면서 작업을 수행해 줍니다. 
• 큐에 값이 없다는 것은 더 이상 이동할 토마토가 없다는 것을 뜻합니다.
• 큐에 값이 있다면 움직인 횟수와 정답을 비교해 줍니다. 
• 비교 후 위, 아래, 상, 하, 좌, 우에 안 익은 토마토가 있다면 체크 후 큐에 값을 넣어 줍니다.
• 반복이 끝난 후 익지 않은 토마토가 있다면 -1을 출력 아닌 경우 정답을 출력해 줍니다.

[코드]

#include<iostream>
#include<queue>
#include<tuple>

using namespace std;


int map[101][101][101];
int visit[101][101][101];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	queue<tuple<int, int, int, int>> que;

	int m, n, h;

	cin >> m >> n >> h;

	for (int k = 0; k < h; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				cin >> map[k][i][j];

				if (map[k][i][j] == 1) {
					que.push(make_tuple(k, i, j, 0));
					visit[k][i][j] = 1;
				}
			}

	int answer = 0;

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

	while (!que.empty()) {

		int hight = get<0>(que.front());
		int x = get<1>(que.front());
		int y = get<2>(que.front());
		int cnt = get<3>(que.front());

		que.pop();

		if (cnt > answer)
			answer = cnt;

		if (hight - 1 >= 0 && visit[hight - 1][x][y] == 0 && map[hight - 1][x][y] == 0) {
			visit[hight - 1][x][y] = 1;
			map[hight - 1][x][y] = 1;
			que.push(make_tuple(hight - 1, x, y, cnt + 1));
		}

		if (hight + 1 < h && visit[hight + 1][x][y] == 0 && map[hight + 1][x][y] == 0){
			visit[hight + 1][x][y] = 1;
			map[hight + 1][x][y] = 1;
			que.push(make_tuple(hight + 1, x, y, cnt + 1));
		}

		for (int i = 0; i < 4; i++) {

			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= m || visit[hight][nx][ny] == 1 || map[hight][nx][ny] == 1 || map[hight][nx][ny] == -1)
				continue;

			map[hight][nx][ny] = 1;
			visit[hight][nx][ny] = 1;
			que.push(make_tuple(hight, nx, ny, cnt + 1));

		}

	}



	for (int k = 0; k < h; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (map[k][i][j] == 0) {
					cout << -1 << endl;
					return 0;
				}
	
	cout << answer << endl;

	return 0;

}