[BOJ] C++ 7569 "토마토" 문제 풀이 _ nov

#INFO

난이도 : GOLD5

문제유형 : BFS

출처 : 7569번: 토마토 (acmicpc.net)

7569번: 토마토

---

#SOLVE

BOJ7576: 토마토 문제와 거의 같은 문제이다. 다른 점 이라면 단지 Z축 좌표가 하나 추가 되었다는 것 뿐이다.

int board[103][103][103] : 토마토의 정보를 저장해 줄 3차원 배열이다.bool isVisited[103][103][103] : 방문 여부를 저장해 줄 3차원 배열이다.int dist[103][103][103] : 거리의 정보를 저장해 줄 배열이다. dist 배열을 이용해 최소 일수를 계산한다.int checked[103][103][103] : 토마토가 모두 익지 못하는 상황을 체크하기 위한 배열이다. int dx[6], dy[6], dz[6] : x, y, z 축으로 이동하는 것을 도와주는 좌표 배열이다.

#define Z first
#define X second.first
#define Y second.second
int board[103][103][103];
bool isVisited[103][103][103];
int dist[103][103][103];
int checked[103][103][103];
int dx[6] = {0, 0, 1, 0, 0, -1};
int dy[6] = {0, -1, 0, 0, 1, 0};
int dz[6] = {1, 0, 0, -1, 0, 0};

 

BFS 알고리즘을 위해 큐를 하나 선언했는데, 평면이 아닌 3차원이기에,  페어에 페어를 중첩시키는 방향으로 문제를 풀이했다. 혹은 STL의 튜플(tuple)을 이용해도 된다. 

	int m, n, h;
	cin >> m >> n >> h;
	queue<pair<int, pair<int, int>>> Q;

 

for 3중첩을 이용해 배열에 정보를 입력받는다.

	for(int k = 0; k < h; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				cin >> board[k][i][j];
				if(board[k][i][j] == 1) {
					isVisited[k][i][j] = 1;
					Q.push({k, {i, j}});
				}
				if(board[k][i][j] == 0) {
					checked[k][i][j] = -1;
				}
			}
		}
	}

 

BFS알고리즘을 수행한다.

	while(!Q.empty()){
		auto cur = Q.front();
		Q.pop();
		for(int dir = 0; dir < 6; dir++){
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			int nz = cur.Z + dz[dir];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m || nz < 0 || nz >= h) continue;
			if(isVisited[nz][nx][ny] || board[nz][nx][ny] != 0) continue;
			dist[nz][nx][ny] = dist[cur.Z][cur.X][cur.Y] + 1;
			isVisited[nz][nx][ny] = 1;
			checked[nz][nx][ny] = 0;
			Q.push({nz, {nx, ny}});
		}
	}

 

마지막으로 day 변수에 거리값을 저장한 후 출력하면 된다.

	int day = 0;
	for(int k = 0; k < h; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(checked[k][i][j] == -1) {
					cout << -1 << '\n';
					return 0;
				}		
				day = max(day, dist[k][i][j]);
			}
		}
	}

	cout << day << '\n';

---

#CODE

#include <bits/stdc++.h>
using namespace std;
#define Z first
#define X second.first
#define Y second.second
int board[103][103][103];
bool isVisited[103][103][103];
int dist[103][103][103];
int checked[103][103][103];
int dx[6] = {0, 0, 1, 0, 0, -1};
int dy[6] = {0, -1, 0, 0, 1, 0};
int dz[6] = {1, 0, 0, -1, 0, 0};

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int m, n, h;
	cin >> m >> n >> h;
	queue<pair<int, pair<int, int>>> Q;
	for(int k = 0; k < h; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				cin >> board[k][i][j];
				if(board[k][i][j] == 1) {
					isVisited[k][i][j] = 1;
					Q.push({k, {i, j}});
				}
				if(board[k][i][j] == 0) {
					checked[k][i][j] = -1;
				}
			}
		}
	}

	while(!Q.empty()){
		auto cur = Q.front();
		Q.pop();
		for(int dir = 0; dir < 6; dir++){
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			int nz = cur.Z + dz[dir];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m || nz < 0 || nz >= h) continue;
			if(isVisited[nz][nx][ny] || board[nz][nx][ny] != 0) continue;
			dist[nz][nx][ny] = dist[cur.Z][cur.X][cur.Y] + 1;
			isVisited[nz][nx][ny] = 1;
			checked[nz][nx][ny] = 0;
			Q.push({nz, {nx, ny}});
		}
	}
	
	int day = 0;
	for(int k = 0; k < h; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(checked[k][i][j] == -1) {
					cout << -1 << '\n';
					return 0;
				}		
				day = max(day, dist[k][i][j]);
			}
		}
	}

	cout << day << '\n';
}