7569

백준 7569번

Link: 7569번: 토마토

---

문제 설명

이번에도 BFS문제다.

저번에 컨디션 아주 별로였던날 한번 보고 어떻게풀지 감이 안와서 포기하고 삼성 기출문제 풀었었는데, 오늘은 마음잡고 제대로 들여다봤다.

백준에는 똑같은 이름의 조금 간단한 문제가 하나 있는데, 이 문제는 그 문제에서 3차원 공간에 대해 생각해보는 요소가 추가된 문제다.

Link: 7576번: 토마토

풀이 방법은 이 문제를 푸는 방법과 크게 다를게 없다.

그저께 풀었던 문제도 그랬는데, 이 문제나 저 문제도 BFS를 통해 트리를 탐색한다고 생각해볼때 몇개의 레벨을 탐색했는지 세면 되는 문제다.

우선 input값이 1인 것들을 visit했다고 표시한 다음 큐에 넣는다.

그리고 BFS를 진행하는데, 우선 트리의 레벨을 세기 위해 큐의 모든 요소들을 벡터에 따로 빼놓고 벡터의 요소들에 대한 BFS를 진행한다.

주의해야 할 점은 3차원적 요소도 고려해야 하는 만큼, 기존 4방향에 더해 위 상자, 아래 상자도 고려하며 구현해야 한다.

이외에는 기존 BFS와 다를 게 없다.

while문을 한번 끝낼때마다 결과값을 1씩 더해주는 식으로 완전탐색을 진행하면 답이 나온다.

나같은 경우에는 결과값의 초기값을 0으로 설정해뒀기 때문에 최종 결과 출력 전에 구한 결과값에서 1을 뺀 값이 맞는 값이다.

BFS가 끝난 후, map에 0이 남아있는지 세보고 결과값을 설정해준 다음 출력해주니 바로 풀렸다.

3차원 배열을 써야 풀릴것 같긴 했는데 시간초과나 메모리초과로 실패하지 않을까 고민하면서 구현했다.

실제로 돌려보니 메모리는 꽤 많이 사용하면서도 시간초과 없이 풀리는걸 보니 아주 무식하게 3차원 배열을 전부 탐색하며 푸는 문제가 맞았던 것 같다.

---

정답 코드

//
// Created by Keith_Lee on 24/01/2019.
//

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int map[100][100][100] = {0, };
bool visit[100][100][100] = {false, };

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int dz[2] = {-1, 1};

// 가로, 세로, 높이
int M, N, H;
int result = 0;

queue<pair<int, pair<int, int>>> Queue;

void BFS(){
    while(!Queue.empty()){
        vector<pair<int, pair<int, int>>> starts;

        while(!Queue.empty()){
            starts.push_back(make_pair(Queue.front().first, make_pair(Queue.front().second.first, Queue.front().second.second)));
            Queue.pop();
        }

        for(int v=0; v<starts.size(); v++){
            int startZ = starts[v].first;
            int startX = starts[v].second.first;
            int startY = starts[v].second.second;

            for(int i=0; i<4; i++){
                int nextX = startX + dx[i];
                int nextY = startY + dy[i];

                if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < M){
                    if(!visit[startZ][nextX][nextY] && map[startZ][nextX][nextY] == 0){
                        visit[startZ][nextX][nextY] = true;
                        map[startZ][nextX][nextY] = 1;
                        Queue.push(make_pair(startZ, make_pair(nextX, nextY)));
                    }
                }
            }

            for(int i=0; i<2; i++){
                int nextZ = startZ + dz[i];

                if(nextZ >= 0 && nextZ < H){
                    if(!visit[nextZ][startX][startY] && map[nextZ][startX][startY] == 0){
                        visit[nextZ][startX][startY] = true;
                        map[nextZ][startX][startY] = 1;
                        Queue.push(make_pair(nextZ, make_pair(startX, startY)));
                    }
                }
            }
        }

        result++;

    }

}

int main(){
    cin >> M >> N >> H;

    // (층, (가로, 세로)) 쌍으로 저장한다.
    vector<pair<int, pair<int, int>>> coordinates;

    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];
                if(map[i][j][k] == 1){
                    visit[i][j][k] = true;
                    Queue.push(make_pair(i, make_pair(j, k)));
                }
            }
        }
    }

    BFS();

    for(int i=0; i<H; i++){
        for(int j=0; j<N; j++){
            for(int k=0; k<M; k++){
                if(map[i][j][k] == 0){
                    result = -1;
                    break;
                }
            }
        }
    }

    if(result != -1){
        cout << result-1 << '\n';
    }
    else{
        cout << -1 << '\n';
    }

    return 0;
}

---