[백준 BOJ][C++]7569번 토마토 풀이: BFS

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

7569번: 토마토

 

[구조체 및 변수 설명]

• box 구조체 : 상자 하나의 토마토 정보와 위치에 해당하는 방문 여부 
• node 구조체 : BFS 에서 queue에 들어갈 노드 정보, 토마토의 x, y, h 위치 정보와 일수를 나타내는 depth
• box boxs[101] : 박스들의 배열
• ans : 일수

 

 

[풀이 과정]

1. m, n, h 입력

2. boxs[] 에 상자와 토마토의 정보 입력

3. 모든 박스의 익은 토마토의 위치를 방문 표시한 후, queue에 푸쉬

4. queue에서 현재 노드 pop

5. 현재 노드에서 상/하/좌/우/앞/뒤 방향이 아직 익지않은 토마토라면 익은 토마토로 변경한 뒤 queue에 푸쉬

6. queue가 empty일 때까지 4~6번 과정 반복

7. BFS 가 완료되면 is_complete() 함수를 호출하여 모든 토마토가 익었는지 확인, 그렇지 않다면 ans = -1

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>

using namespace std;

typedef struct box {
	vector<vector<int>> data;
	bool visit[101][101] = { false, };
};

typedef struct node {
	int x;
	int y;
	int h;
	int depth;
};

int m, n, h; //가로, 세로, 높이
box boxs[101];
int ans;

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

bool is_complete() {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				if (boxs[i].data[j][k] == 0)
					return false;
			}
		}
	}
	return true;
}

void bfs() {

	queue<node> q;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				if (boxs[i].data[j][k] == 1) {
					boxs[i].visit[j][k] = true;
					q.push({ k, j, i, 0 });
				}
			}
		}
	}

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

		ans = max(ans, curr.depth);

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

			if (tx < 0 || tx >= m || ty < 0 || ty >= n
				|| th < 0 || th >= h)
				continue;
			if (boxs[th].visit[ty][tx] || boxs[th].data[ty][tx] == -1 ||
				boxs[th].data[ty][tx] == 1)
				continue;

			boxs[th].visit[ty][tx] = true;
			boxs[th].data[ty][tx] = 1;
			q.push({ tx, ty, th, curr.depth + 1 });
		}
	}

	if (!is_complete())
		ans = -1;
}

int main(void) {
	cin >> m >> n >> h;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			vector<int> temp;
			for (int k = 0; k < m; k++) {
				int x;
				cin >> x;
				temp.push_back(x);
			}
			boxs[i].data.push_back(temp);
		}
	}

	bfs();

	cout << ans;

	return 0;
}