[BOJ] 7569번 토마토 문제풀이 (C++)

2018.1.3 에 쓰여진 글 입니다.

---

문제링크

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

7569번: 토마토

 

풀이방법

일단 이문제는 

https://royhelen.tistory.com/19

[BOJ] 7576번 토마토 문제풀이 (C++)

7576 토마토에서 업그레이드 된 문제이다.

풀이는 다똑같은데 이번에는 높이까지 추가된것이 포인트!!

이것말고는 딱히 다른게 없음..

(자세한건 코드의 주석을 보면서 참고하면 될 듯... 합니다. )

 

소스코드

#include <iostream>
#include <queue>
#include <utility>
 
using namespace std;
 
enum { EMPTY = -1, TOM_X = 0, TOM_O = 1 };
 
int N, M, H;
int map[100][100][100];
queue < pair < int , pair < int, int > > > q;
int q_count;    //큐 크기 저장. 해당일에 현재 익어있는 토마토 갯수에서 퍼뜨릴 갯수 체크하는 카운트
int day;        //날짜수
int dh[] = { -1,1,0,0,0,0 };        //방향 6개로 설정 
int dx[] = { 0,0,-1,0,1,0 };
int dy[] = { 0,0,0,-1,0,1 };
 
void Init_map()
{
    for (int h = 0; h < H; h++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                map[i][j][h] = EMPTY;
}
 
void solve()
{
    while (!q.empty() && q_count > 0) {
        int cur_h = q.front().first;            //현재 익은 토마토 좌표를 꺼내서 저장
        int cur_x = q.front().second.first;
        int cur_y = q.front().second.second;
        q.pop();        //큐하나빼줌
        for (int i = 0; i < 6; i++) {
            int new_h = cur_h + dh[i];        //상하좌우 위아래 다돌릴꺼
            int new_x = cur_x + dx[i];
            int new_y = cur_y + dy[i];
            if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < M && 0 <= new_h&&new_h < H&&
                map[new_x][new_y][new_h] == TOM_X) {    //범위안에있고 해당 토마토가 익어있지않다면
                map[new_x][new_y][new_h] = TOM_O;        //익혀줌 
                q.push(make_pair(new_h, make_pair(new_x, new_y)));        //그 익힌좌표를 다시 큐에 삽입
            }
        }
        q_count--;    //큐카운트 줄여줌
    }
}
 
bool check()
{
    for (int h = 0; h < H; h++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (map[i][j][h] == TOM_X)
                    return false;
    return true;
}
 
int main()
{
    cin >> M >> N >> H;
    Init_map();        //맵초기화
    day = 0;        //만약 다익어있다면 하루도 
    q_count = 0;    //큐카운트초기화
    for (int h = 0; h < H; h++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) {
                cin >> map[i][j][h];
                if (map[i][j][h] == TOM_O)        //익은 토마토가 있다면
                    q.push(make_pair(h, make_pair(i, j)));    //해당 큐에 좌표를 넣어준다
            }
    while (!q.empty()) {
        q_count = q.size();        //현재 큐크기를 q_count에 넣어준다. 
                                //해당 날짜에 익혀야되는 좌표갯수를 체크(?) 
                                //백준 테케를 예를 들면 1이 4개니까 첫째날에 4개를 퍼뜨릴꺼임 그 갯수를 체크
                                //둘째날에도 4개가될꺼임 
        solve();    //solve함수 호출
        day++;        //날짜하루씩지남
    }
    day--;        //마지막익은토마토일때도 하루가더해졌을테니까 그거하루빼줌
    if (!check())
        day = -1;        //만약안익은 토마토가 있다면 -1을 day에 대입
    cout << day << endl;    //정답출력
    
    return 0;
}