[BOJ] 7576 토마토

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

문제를 요약하자면 익은 토마토가 토마토 상자에 있는 모든 토마토를 익히는 데 까지 얼마나 걸리는지 확인하는 것입니다.

바이러스가 퍼지듯이 동시다발적으로 퍼지는 것이라 주요 논점은 DFS가 아닌 BFS를 활용해야한다는 점입니다.

---

문제 핵심 IDEA

토마토 문제의 핵심아이디어라면 당연히 위에 말했듯이 BFS입니다.

하지만 제일 큰 고민점은 BFS를 진행할 때마다 날짜 카운트를 해주는 건 아니라는 것입니다.

BFS에서 다루는 것중 하나인 Level을 체크해주는 것이 곧 날짜 카운트와 동일합니다.

제가 문제 풀때 발생했던 실수와 해결책은 생각 흐름 파트에서 설명해드리겠습니다.

---

생각흐름

기초 흐름

토마토는 사실 BFS문제로 유명한 문제입니다. 그런 이유로 보자마자 BFS설계를 한 것도 있습니다.

하지만 그걸 몰라도 BFS임을 알 수 있는 이유는 다음과 같습니다.

[ BFS인 이유 ]

1. 전체 토마토상자(map)를 모두 탐색을 해야 한다.
2. 단순하게 상자를 탐색하는 것이 목적이 아닌 "최단 시일"을 찾아야 하는 게 핵심이다.
3. 토마토가 퍼지는 것은 인접한 위치가 "동시 다발"적으로 진행된다.

흔히 BFS에서 Level을 체크하는 것은 최단 경로를 찾는 느낌과 비슷하기에 level을 계산해주는 코드로 작성을 해줍시다.

while문 안에 for문을 큐의 크기만큼 반복해주고 for문의 종료 이후 날짜 카운트를 올려주면 됩니다.

토마토 상자는 map으로 하겠습니다.

첫번째 접근

1. 맨 처음에는 2차원 배열을 2개 만들어서 원본 map은 1이 있는 위치만 저장해서 확인하는 역할을 하고 사본 map에서 탐색을 진행하려고 했습니다. 근데 생각해보니까 굳이 그렇게 할 이유가 없더군요. 사실 메모리 관리도 중요하니까요. 그래서 저는 start라는 큐에 시작 위치 i, j를 저장하고 그걸 BFS에서 사용하는 Q에 넣었습니다. 사실 이 부분도 메모리 낭비죠.

두번째 접근

1. 일반적인 BFS를 진행하는 데 문제가 발생했습니다. 백준 예제 중 하나가 익는 데 시간이 없으므로 0일이 나와야 하는 데 무조건 레벨 체크를 하다 보니 1이 나왔습니다. 이를 해결하기 위해서 BFS가 한 번이라도 돌면 카운터를 올려줘서 카운터가 0이 아니면 날짜 카운트를 올려주게 했습니다. 문제가 발생한 예제는 BFS를 한 번도 돌리지 않기 때문에 날짜 카운트가 skip 됩니다.

세번째 접근

1. 이제 날짜를 어떻게 기록할지가 문제가 발생했었습니다. 가장 처음 작성한 코드는 단순히 날짜를 출력하게 했습니다. 그랬더니 1일이 더 많게 나왔습니다. 이유를 확인해보니까 마지막에도 BFS가 돌게 되지만 맵상에 모든 토마토는 꽉 차거나 접근 불가능한 영역에 있게 됩니다. 이런 경우 결국 레벨을 체크한 것이므로 마지막 레벨이 1번 더 돌게 됩니다. 그래서 날짜 카운트가 1이 추가가 된 것입니다. 그걸 해결하기 위해서 그냥 BFS가 돌 때마다 해당 레벨의 날짜 카운터를 맵에 기록해서 채웠습니다. 사실 0만 아니면 익은 거로 취급이 가능하니까요.

최종적으로는 map을 이중 for문으로 쭉 훑으면서 최고 값을 답으로 기록하면 됩니다.

---

정답 코드

#include <iostream>
#include <queue>
#include <queue>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> P; // P(i, j) = (y, x)
const int dirx[4] = {0,0,1,-1};
const int diry[4] = {-1,1,0,0};
int map[1001][1001];
int N, M;
bool visit[1001][1001];
int day = 0;
int cnt = 0;
queue<P> start;
queue<P> Q;

void BFS() {
    visit[Q.front().first][Q.front().second] = true;

    while (!Q.empty()) {
        int qsize = Q.size();

        for (int i = 0; i < qsize; i++) {
            int x = Q.front().second;
            int y = Q.front().first;
            Q.pop();

            if (map[y][x] == 0) // In BFS, It means adjenct tomato
                map[y][x] = day;

            for (int i = 0; i < 4; i++) {
                int nx = x + dirx[i];
                int ny = y + diry[i];

                if (ny >= 0 && ny < M && nx >= 0 && nx < N) {
                    if (map[ny][nx] == 0 && !visit[ny][nx]) {
                        cnt++;
                        visit[ny][nx] = true;
                        Q.push(P(ny, nx));
                    }
                }
            }
        }

        if (cnt != 0) {
            day++;
        }

    }
}


int main() {

    cin >> N >> M;

    // map making
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];

            if (map[i][j] == 1)
                start.push(P(i,j)); // start point save queue
        }

    int iter = start.size();


    Q = start;
    BFS();


    int ans = 0;
    bool answerflag = true; // if ans = true

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 0) {
                answerflag = false;
                break;
            }
            ans = max(ans,map[i][j]);
        }

        if (!answerflag)
            break;
    }

    if (cnt == 0) {
        ans = 0;
    }

    if (!answerflag) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }

}

일부 좀 불필요한 코드들도 있다고 생각을 하지만 제가 생각한 방법은 이게 최선인 것 같네요.

나중에 좀 더 실력이 늘면 달라질 수도…?

GitHub - https://github.com/cow-coding/algorithm/blob/master/BOJ/C%2B%2B/7576.cpp