[BOJ] 7569 토마토

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

7569번: 토마토

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

bfs

 

---------------------------------------------------풀이----------------------------------------------------

 

map[H][X][Y]를 저장하는 삼차원 array를 선언해 실제 토마토가 위치하는 곳을 구조화 하였다.

 

map[][][] == 0인 익어야하는 토마토의 개수를 to_be_num으로 저장하고, 토마토가 익을 때마다(0->1로 바뀔 때마다) 이 값을 1 감소시켜 모든 토마토가 익었는지를 체크할 수 있도록 했다.

 

매번 100x100x100의 map을 조사하며 새로 익을 토마토를 찾는 방식은 비효율적이므로,

queue<Tomato> q를 정의해 하루마다 새로 익은 토마토를 저장하였다.

이 토마토의 주변 6방향의 토마토는 전부 체크되어 그 중 새로 익은 토마토들만 다시 q에 들어있도록 하였기 때문에,

매번 q에는 이전 날에 새로 익은 토마토만 저장된다.

즉, 경계에 있는 새로 익은 토마토만 q에 저장된다.

하루마다 q의 모든 토마토의 주변을 조사해 새로 익을 토마토가 있다면(map[][][] == 0) 토마토를 익히고(map[][][] = 1)

이 토마토를 날마다 리셋되는 next_q에 저장한다.

q의 모든 토마토를 조사하면(q.empty() == true) q에 next_q의 값을 복사하고(q = next_q) 다음 날로 넘어간다.

 

이 과정을 q가 next_q의 값을 복사하더라도 비어있거나, 익어야 하는 토마토의 개수인 next_tomato가 0이 될 경우까지 반복한다.

만약, 이 과정이 끝났는데 next_tomato가 0이 아니면 모든 토마토를 익히는 것이 불가능하다는 것이므로 -1을, 아니면 날짜(ans)를 리턴한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <deque>

using namespace std;

typedef struct{
    int x, y, h;
} Tomato;

int N, M, H;
int map[101][101][101] = {0, };
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
// 익어야 하는 토마토의 수
int to_be_num = 0;
// 새로 익은 토마토
queue<Tomato> q;

int solution(){
    Tomato cur;
    int ans = 0;

    queue<Tomato> next_q;
    // 새로 익은 토마토가 남아있고, 익어야 하는 토마토가 있는 경우
    while(!q.empty() && to_be_num){
        ans++;
        while(!next_q.empty()){
            next_q.pop();
        }
        while(!q.empty()){
            cur = q.front();
            q.pop();
            // 여섯 방향 익히기 시도
            int nx, ny;
            for(int i = 0; i < 4; i++){
                nx = cur.x + dx[i];
                ny = cur.y + dy[i];
                if(nx < 0 || nx >= N || ny < 0 || ny >= M || map[cur.h][nx][ny] != 0){
                    continue;
                }
                map[cur.h][nx][ny] = 1;
                Tomato new_tomato;
                new_tomato.h = cur.h; new_tomato.x = nx; new_tomato.y = ny;
                next_q.push(new_tomato);
                to_be_num--;
            }
            if(cur.h-1 >= 0 && map[cur.h-1][cur.x][cur.y] == 0){
                Tomato new_tomato = cur;
                new_tomato.h--;
                map[new_tomato.h][new_tomato.x][new_tomato.y] = 1;
                next_q.push(new_tomato);
                to_be_num--;
            }
            if(cur.h+1 <= H-1 && map[cur.h+1][cur.x][cur.y] == 0){
                Tomato new_tomato = cur;
                new_tomato.h++;
                map[new_tomato.h][new_tomato.x][new_tomato.y] = 1;
                next_q.push(new_tomato);
                to_be_num--;
            }
        }
        q = next_q;
    }

    // 익을 수 있는 토마토는 없지만, 익어야 하는 토마토가 남은 경우 -1 리턴.
    if(to_be_num > 0){
        return -1;
    }
    else{
        return ans;
    }
}

int main(void){
    FASTIO;
    cin >> M >> N >> H;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < N; j++){
            for(int k = 0; k < M; k++){
                cin >> map[i][j][k];
                Tomato t;
                if(map[i][j][k] == 0){
                    to_be_num++;
                }
                else if(map[i][j][k] > 0){
                    t.h = i; t.x = j; t.y = k;
                    q.push(t);
                }
            }
        }
    }
    cout << solution() << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

이전 토마토 익히기 문제의 심화 버전으로, 달라진 점은 h값도 생각해줘야 한다는 점이다.

이전에 풀었던 방식에서 변형해, 현재 익어야하는 남은 토마토 개수를 이용해 모든 토마토가 익었는지를 체크했다.

이전에는 is_complete()라는 함수에서 모든 map을 돌며 남은 토마토가 있는지를 체크했다.