(cpp) Baekjoon 7569번 문제 ‘토마토’ - 그래프 이론, 그래프 탐색, 너비 우선 탐색 (토마토7576과 다른 ver)
Baekjoon 7569번 문제 ‘토마토’ - 그래프 이론, 그래프 탐색, 너비 우선 탐색
예제입력2에 대한 문제풀이
1. 익은 토마토가 있는 칸부터 시작한다. 7576번 토마토 문제는 2차원 배열이였으나 이번엔 상자를 위로 쌓아올리는 3차원 배열이다. 따라서, 토마토의 위치는 [i,j.k]로 표현한다. 순서대로, 높이,행,열 이다. 즉 예제2번의 시작큐는 = [2,2,3]이다. ‘2층의 2행 3열’이라는 의미.
2. [2,2,3]에서 시작했을 때 갈 수 있는 곳은 왼[2,2,2],오[2,2,4],위[2,1,3],아[2.3,3],아래층[1,2,3]이다. 칸의 위치가 3차원 배열인 것과 방문 후보가 4개에서 6개로 늘었다는 것 외에는 7576번과 같은 방식으로 해결할 수 있다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
using namespace std;
int m, n, h, state, g[101][101][101];
int result = 0;
// 왼,오,위,아,위층,아래층
int h_pos[6] = { 0,0,0,0,-1,1 };
int r_pos[6] = { 0,0,-1,1,0,0 };
int c_pos[6] = { -1,1,0,0,0,0 };
struct tomato {
int h,r,c;
};
queue<tomato> q;
void solution() {
while (!q.empty()) {
int cur_h = q.front().h;
int cur_r = q.front().r;
int cur_c = q.front().c;
q.pop();
for (int i = 0; i < 6; i++) {
int next_h = cur_h + h_pos[i];
int next_r = cur_r + r_pos[i];
int next_c = cur_c + c_pos[i];
if (0 < next_r && next_r <= n && 0 < next_c && next_c <= m && 0 < next_h && next_h <= h && g[next_h][next_r][next_c] == 0) {
g[next_h][next_r][next_c] = g[cur_h][cur_r][cur_c] + 1;
q.push({ next_h,next_r,next_c});
}
}
}
}
int main() {
cin >> m >> n >> h;
for (int i = 1; i <= h ; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= m; k++) {
cin >> state;
g[i][j][k] = state;
if (g[i][j][k] == 1) {
q.push({ i,j,k }); //state가 1인 시작점 큐에 입력
}
}
}
}
solution();
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= m; k++) {
if (g[i][j][k] == 0) {
cout << -1;
return 0;
}
if (g[i][j][k] > result) {
result = g[i][j][k];
}
}
}
}
cout << result-1;
return 0;
}
- 조건문에서 수의 범위를 조건으로 넣을 때 ‘0 < next_h <= h’로 넣으면 안된다. ‘0 < next_h && next_h <= h’로 나눠 넣어야 함.
- 다차원 배열에서 왼쪽에 있을수록 큰 묶음이다. 1층의 3행 2열이면 g[1][3][2] 로 써야함
- 그에 따라, 초기 그래프 크기도 g[h][r][c]로 설정해야 한다. g[101][101][101]로 해주었음.