[BOJ] 백준 7569 토마토

문제 분석 및 링크

[ 백준 / 7569 ] 토마토

7569번: 토마토

BFS를 이용해서 푸는 대표적인 문제입니다. 7576번 토마토 문제는 가로와 세로 2차원만 고려했다면 이 토마토 문제는 높이까지 3차원으로 고려해주어야 합니다. 푸는 방식 자체는 이동 방향 설정 및 배열 선언만 잘해준다면 7576번 문제와 크게 차이가 없습니다. dx, dy와 추가로 dh 배열을 하나 더 만들어주었고, 높이의 정보 담기 위해서 3차원 배열을 사용하였습니다.

 

문제 소스 코드

#include <cstdio>
#include <queue>

using namespace std;

queue<pair<pair<int, int>, int>> q;
int m, n, h;
int tomato[101][101][101];

// 가로 세로 높이 이동 방향 지정
int dx[6] = { 0,0,-1,1,0,0 }; 
int dy[6] = { -1,1,0,0,0,0 };
int dh[6] = { 0,0,0,0,1,-1 };


void bfs() {
	while (!q.empty()) {
		int curx = q.front().first.first; 
		int cury = q.front().first.second;
		int curh = q.front().second;

		q.pop();
		for (int i = 0; i < 6; i++) {
			int nextx = curx + dx[i];
			int nexty = cury + dy[i];
			int nexth = curh + dh[i];

			if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m || nexth < 0 || nexth >= h) continue;
			
            // 다음 위치가 0이라면 현재 위치 +1의 값을 대입
			if (tomato[nexth][nextx][nexty] == 0) {
				tomato[nexth][nextx][nexty] = tomato[curh][curx][cury] + 1;
				q.push(make_pair(make_pair(nextx, nexty), nexth));
			}
		}

		
	}
}
int main(void) {
	scanf("%d%d%d", &m, &n, &h);
	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				scanf("%d", &tomato[k][i][j]);
				
                // 1인 경우 미리 queue에 저장
				if (tomato[k][i][j] == 1) q.push(make_pair(make_pair(i, j), k));
			}
		}
	}

	bfs();
	int result = 0;
	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
            	// 익지 않은 토마토가 있을 경우 -1을 출력 후 종료
				if (tomato[k][i][j] == 0) {
					printf("%d", -1);
					return 0;
				}
                // bfs를 거친 tomato 배열에서 가장 큰 값을 저장
				if (tomato[k][i][j] > result) {
					result = tomato[k][i][j];
				}
			}
		}
	}

	printf("%d\n", result - 1);

	
}

개발 환경 : Visual Studio 2019