[BFS]BAEKJOON7569 - 토마토(복층구조)

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

 

이 문제는 BFS문제 중에서는 기초적인 문제이지만 조금 더러운 문제중 하나이기도하다.

그 이유는 이 문제에서는 여러가지 해결법이 다 통하는 문제는 아니기 때문이다.

이 문제의 의도는 "정석 BFS로 풀어라!"라는 문제이다.

그 이유는 풀면서 설명하겠다.

 

가로 M, 세로 N, 높이는 H이다.

그리고 하나의 토마토가 익게되면 주위의 토마토도 같이 익게된다.

이 때 익은 토마토는 1, 안 익은 토마토는 0, 토마토가 없는 칸은 -1이 된다.

 

이 문제는 DFS와 BFS모두 접근은 가능한데 실제로는 DFS로는 거의 못푸는 문제이다.

그 이유는 DFS로 풀게되면 엄청나게 반복을 하기 때문이다.

즉 시간을 미친듯이 잡아먹는다. 그래서 BFS로 푸는것이 좋다.

 

첫 예제로 보도록하자.

 

1)
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

2)
0 -1 0 1 1
-1 -1 1 1 1
0 0 1 1 1

3)
0 -1 1 1 1
-1 -1 1 1 1
0 1 1 1 1

4)
0 -1 1 1 1
-1 -1 1 1 1
1 1 1 1 1

실패

 

첫 예제를 보면 0이 결국 하나 남기 때문에 모두 익히지 못한다.

그래서 -1이 출력된다.

두번 째예제를 보자.

 

1)
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

2)
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
-
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0

3)
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
-
0 1 1 1 0
1 1 1 1 1
0 1 1 1 0

4)
0 1 1 1 0
1 1 1 1 1
0 1 1 1 0
-
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

5)
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
-
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

4번만에 성공

 

두번째는 총 4번만에 성공하게된다.

BFS로만 구현하면 되므로 난이도 자체는 높지는 않다.

문제는 BFS를 아느냐 모르느냐겠지만.

 

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

using namespace std;

class Point {
public:
    int m;
    int n;
    int h;

    Point(int m, int n, int h) : m(m), n(n), h(h) {}

    Point() : m(0), n(0), h(0) {}
};

ostream &operator<<(ostream &o, Point p) {
    o << "m:" << p.m << ", n:" << p.n << ", h:" << p.h;
    return o;
}

int M, N, H;
vector<vector<vector<int>>> map;
queue<Point> q;
int tmp;
Point tp;
int result = 1;
int remain = 0;
bool sw;

void print() {
    for (int h = 1; h <= H; h++) {
        for (int n = 1; n <= N; n++) {
            for (int m = 1; m <= M; m++) {
                cout << map[m][n][h] << " ";
            }
            cout << endl;
        }
    }
}

int main() {
    //init
    {
        cin >> M >> N >> H;
        map.resize(M + 1, vector<vector<int>>(N + 1, vector<int>(H + 1, 0)));
        for (int h = 1; h <= H; h++) {
            for (int n = 1; n <= N; n++) {
                for (int m = 1; m <= M; m++) {
                    cin >> tmp;
                    map[m][n][h] = tmp;
                    if (tmp == 1) {
                        q.push(Point(m, n, h));
                    } else if (tmp == 0) {
                        remain++;
                    }
                }
            }
        }
    }

    //logic
    {
        while (!q.empty()) {
            tp = q.front();
            q.pop();
            sw = false;
            if (0 < tp.m - 1 && map[tp.m - 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m - 1, tp.n, tp.h));
                map[tp.m - 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.m + 1 <= M && map[tp.m + 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m + 1, tp.n, tp.h));
                map[tp.m + 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.n - 1 && map[tp.m][tp.n - 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n - 1, tp.h));
                map[tp.m][tp.n - 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.n + 1 <= N && map[tp.m][tp.n + 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n + 1, tp.h));
                map[tp.m][tp.n + 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h - 1));
                map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.h + 1 <= H && map[tp.m][tp.n][tp.h + 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h + 1));
                map[tp.m][tp.n][tp.h + 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            result = sw ? max(result, map[tp.m][tp.n][tp.h] + 1) : result;
        }
    }

    //output
    {
        if (remain == 0) {
            cout << result - 1 << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

코드를 보면 간단하다.

여기서 디버깅용 로직들을 제외하면 다음과 같다.

 

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

using namespace std;

class Point {
public:
    int m;
    int n;
    int h;

    Point(int m, int n, int h) : m(m), n(n), h(h) {}

    Point() : m(0), n(0), h(0) {}
};

int M, N, H;
vector<vector<vector<int>>> map;
queue<Point> q;
int tmp;
Point tp;
int result = 1;
int remain = 0;
bool sw;

int main() {
    //init
    {
        cin >> M >> N >> H;
        map.resize(M + 1, vector<vector<int>>(N + 1, vector<int>(H + 1, 0)));
        for (int h = 1; h <= H; h++) {
            for (int n = 1; n <= N; n++) {
                for (int m = 1; m <= M; m++) {
                    cin >> tmp;
                    map[m][n][h] = tmp;
                    if (tmp == 1) {
                        q.push(Point(m, n, h));
                    } else if (tmp == 0) {
                        remain++;
                    }
                }
            }
        }
    }

    //logic
    {
        while (!q.empty()) {
            tp = q.front();
            q.pop();
            sw = false;
            if (0 < tp.m - 1 && map[tp.m - 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m - 1, tp.n, tp.h));
                map[tp.m - 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.m + 1 <= M && map[tp.m + 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m + 1, tp.n, tp.h));
                map[tp.m + 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.n - 1 && map[tp.m][tp.n - 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n - 1, tp.h));
                map[tp.m][tp.n - 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.n + 1 <= N && map[tp.m][tp.n + 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n + 1, tp.h));
                map[tp.m][tp.n + 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h - 1));
                map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.h + 1 <= H && map[tp.m][tp.n][tp.h + 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h + 1));
                map[tp.m][tp.n][tp.h + 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            result = sw ? max(result, map[tp.m][tp.n][tp.h] + 1) : result;
        }
    }

    //output
    {
        if (remain == 0) {
            cout << result - 1 << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

그럼 설명을 시작하겠다.

 

class Point {
public:
    int m;
    int n;
    int h;

    Point(int m, int n, int h) : m(m), n(n), h(h) {}

    Point() : m(0), n(0), h(0) {}
};

먼저 큐에 좌표의 정보를 담아야하니까 클래스를 만들어준다.

물론 클래스를 만들지 않아도 되지만 개인적으론 안만드는게 더 힘들 거 같다.

 

//init
    {
        cin >> M >> N >> H;
        map.resize(M + 1, vector<vector<int>>(N + 1, vector<int>(H + 1, 0)));
        for (int h = 1; h <= H; h++) {
            for (int n = 1; n <= N; n++) {
                for (int m = 1; m <= M; m++) {
                    cin >> tmp;
                    map[m][n][h] = tmp;
                    if (tmp == 1) {
                        q.push(Point(m, n, h));
                    } else if (tmp == 0) {
                        remain++;
                    }
                }
            }
        }
    }

초기화 로직도 중요한데

다른게 아니라 바로 remain이라는 변수의 존재이다.

우리는 성공했을 때와 실패했을 때를 구별해야한다.

즉 모든 BFS를 돌았을 때 0이 남지 않아야한다.

0이 남으면 실패한것인데 이걸 해결할 수 있는 방법은 2가지가 있다.

 

하나는 이렇게 미리 0의 갯수를 새고 익은녀석마다 0의 갯수를 지우는 것,

또다른 것은 BFS가 끝나고 마지막에 0의 갯수를 새는 것이다.

물론 시간복잡도는 똑같으니 뭘해도 상관없지만 깔끔하게 하고싶다면 위 방법을 추천한다.

 

bool chkAll() {
    bool result = true;
    for (int h = 1; h <= H; h++) {
        for (int n = 1; n <= N; n++) {
            for (int m = 1; m <= M; m++) {
                if (map[m][n][h] == 0) {
                    result = false;
                }
            }
        }
    }
    return result;
}

만약 마지막에 0의 갯수를 새고 싶다면 위처럼 사용해주면 된다.

 

//logic
    {
        while (!q.empty()) {
            tp = q.front();
            q.pop();
            sw = false;
            if (0 < tp.m - 1 && map[tp.m - 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m - 1, tp.n, tp.h));
                map[tp.m - 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.m + 1 <= M && map[tp.m + 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m + 1, tp.n, tp.h));
                map[tp.m + 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.n - 1 && map[tp.m][tp.n - 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n - 1, tp.h));
                map[tp.m][tp.n - 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.n + 1 <= N && map[tp.m][tp.n + 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n + 1, tp.h));
                map[tp.m][tp.n + 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h - 1));
                map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.h + 1 <= H && map[tp.m][tp.n][tp.h + 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h + 1));
                map[tp.m][tp.n][tp.h + 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            result = sw ? max(result, map[tp.m][tp.n][tp.h] + 1) : result;
        }
    }

로직은 길어 보이지만 간단하다.

그냥 BFS를 돌리는 로직이며 마지막에 result는 현재 level이 최고 level보다 크다면 갱신시켜주는 작업이다.

 

보통 BFS를 돌릴 때 level정보는 저장하는 방법이 두가지가 있다.

하나는 좌표(Graph나 map)에 직접 적는 방법과 클래스(위의 경우 Point)에 레벨 변수를 두고 넣는 방법이다.

이 문제가 더러운 이유는 레벨 변수를 둘 수가 없기 때문이다.

그래서 좌표에 직접 써야한다.

따라서 위의 경우 익으면 1이 아니라 익으면 1 이상이 들어가게 로직이 짜져있다.

 

if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
    q.push(Point(tp.m, tp.n, tp.h - 1));
    //map[tp.m][tp.n][tp.h - 1] = 1;
    map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
    sw = true;
}

가령 하나를 예를 들어서 3번째 줄을 보면 위의 코드는 만약 현재 탐색하려는 좌표가 빈공간이면

지금 좌표의 값에 1을 더해주는 로직이다.

원래라면 주석처리한것 처럼 해도 되지만 이 경우 현재 레벨에 대한 정보는 소실된다.

즉 지금 일어난 루프가 몇번째 레벨인지를 알 도리가 없다.

이 경우 클래스에 저장해 두는데 이게 메모리 제한으로 막아놨다.

그래서 우리는 현재 레벨에 대한 정보를 좌표에 저장해둔다(위의 예제는 변수 map).

 

//output
    {
        if (remain == 0) {
            cout << result - 1 << endl;
        } else {
            cout << -1 << endl;
        }
    }

그래서 마지막에 결과에서 1을 뺀다.

왜냐하면 기존 토마토가 존재한다는걸 좌표에서 1로 표현,

그 다음은 1씩 증가하게 되는데 결과 값에서 기존의 값 1이 최대값이므로 1을 빼줘야하기 때문이다.