[C++] 백준 7576 : 토마토
#include <iostream>
#include <utility> //pair
#include <queue>
using namespace std;
int map[101][101][101]; // 1 : 익은 토마토, 0 : 익지 않은 토마토, -1 : 토마토 없음
queue<pair<pair<int, int>, int> > q; // h, y, x
// 상하좌우위아래 탐색
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dh[6] = {0, 0, 0, 0, 1, -1};
bool allTomato = true; // 모든 토마토 익어있는 경우
int M, N, H; // 가로, 세로, 높이
int cnt = 0; // 토마토 모두 익을 때 까지 걸리는 시간
void BFS(){
while(!q.empty()){
int x = q.front().second;
int y = q.front().first.second;
int h = q.front().first.first; // 노드의 좌표 구하기
q.pop();
for(int i = 0; i < 6; i++){
int nx = x + dx[i];
int ny = y + dy[i];
int nh = h + dh[i];
if(nx < 1 || ny < 1 || nh < 1 || nx > M || ny > N || nh > H){
continue;
}
if(map[nh][ny][nx] == 0){ // 안익은 토마토가 있을 때
map[nh][ny][nx] = map[h][y][x] + 1; // 날짜 더하기
q.push({{nh, ny}, nx});
}
}
}
}
int main(int argc, char* argv[]){
scanf("%d %d %d", &M, &N, &H);
for(int i=1; i<=H; i++){
for(int j=1; j<=N; j++){
for(int k=1; k<=M; k++){
scanf("%d", &map[i][j][k]); // 입력받기
if(map[i][j][k] == 1){ // 익은 토마토일 때
q.push({{i, j}, k});
} else if(map[i][j][k] == 0){
allTomato = false;
}
}
}
}
if(allTomato){ // 처음부터 모든 토마토 익어있는 경우
printf("0");
return 0;
}
BFS();
// for(int i=1; i<=H; i++){
// for(int j=1; j<=N; j++){
// for(int k=1; k<=M; k++){
// printf("%d ", map[i][j][k]);
// }
// printf("\n");
// }
// }
for(int i=1; i<=H; i++){
for(int j=1; j<=N; j++){
for(int k=1; k<=M; k++){
if(map[i][j][k] == 0){ // 모두 익지 않았을 때
printf("-1");
return 0;
}
if(cnt < map[i][j][k]){ // 최대 일 수 구하기
cnt = map[i][j][k];
}
}
}
}
printf("%d", cnt-1); // 토마토 익은 것 1부터 시작
return 0;
}
7576 토마토의 업그레이드 버전 문제
-
상하좌우위아래 를 확인하기 위해서는 위로 갈 경우, 아래로 갈 경우, 좌로 갈 경우, 우로 갈 경우... 해서 6가지의 경우 수만 확인하면 된다. 이걸 조심하자. 처음에는 모든 경우의 수를 내가 배열에 넣어서 구하려고 했는데 굉장히 불필요한 일이었다.
-
cnt를 세기 위해 바로 map으로 표시했기에 visit 여부는 표시할 필요가 없다. 때문에 7576 번에서 푼 것과 다르게 이번에는 visited를 아예 빼버렸다.
-
pair에 값을 입력할 때, make_pair를 쓰는 것도 좋지만 {}를 쓰는 것이 훨씬 직관적이며 쉽다.
Author And Source
이 문제에 관하여([C++] 백준 7576 : 토마토), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-7576-토마토-7en3569n저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)