[BOJ] 7576 토마토

1. 문제링크

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

2.해설

이 문제는 전형적인 BFS문제이다.

문제 풀이 순서는 이러하다.

1. 시작점을 찾는다.

2. BFS로 가능한 만큼 토마토를 다 익힌다.

3. 다 익었는지 확인 하고 다 익었다면 구한 cnt를 ans에 대입하고 출력한다.

시간복잡도는 BFS의 시간복잡도인 O(VE) 이고 이 문제에서는 O(n^2) 이다.

3. 소스코드

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define MAXNUM 1010

struct point{
    int x, y;
};

bool isRipe(int n, int m, int tomato[][MAXNUM]);

int main(){
    int n, m, ans=-1, cnt=0;
    int tomato[MAXNUM][MAXNUM]={0};
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    queue<point> q;
    memset(tomato, -1, sizeof(tomato));
    
    scanf("%d %d", &m, &n);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            scanf("%d", &tomato[i][j]);
            //시작 지점 push
            if (tomato[i][j] == 1) q.push({j, i});
        }
    }
    
    while (!q.empty()) {
        int size = (int)q.size();
        cnt++;
        for (int l=0; l<size; l++) {
            point cur = q.front(); q.pop();
            //상하좌우 4방향 확인하고...
            for (int i=0; i<4; i++) {
                point next = {cur.x + dx[i], cur.y + dy[i]};
                //안 익은 토마토라면 큐에 push한다.
                if (tomato[next.y][next.x] == 0) {
                    tomato[next.y][next.x] = 1;
                    q.push(next);
                }
            }
        }
    }
    
    if (isRipe(n, m, tomato)) {
        ans = cnt-1;
    }
    
    printf("%d\n", ans);
    
    return 0;
}
//다 익었는지 확인
bool isRipe(int n, int m, int tomato[][MAXNUM]){
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            if (tomato[i][j] == 0) {
                return false;
            }
        }
    }
    return true;
}

4. 추가 언급

BFS문제들은 조금만 실수해도 메모리가 터진다거나, 시간이 터지는 경우가 굉장히 많다. 이 토마토 문제도 언제 익었다라고 확인 해주는 가에 따라서 메모리가 터질 수도 안 터질 수도 있다. 우리는 queue에 넣을 때 익었다 라고 확인을 해준다. 그렇다면 while문을 이렇게 바꾸면 어떻게 될까. 한번 생각해보자.

while (!q.empty()) {
        int size = (int)q.size();
        cnt++;
        for (int l=0; l<size; l++) {
            point cur = q.front(); q.pop();
            tomato[cur.y][cur.x] = 1;
            //상하좌우 4방향 확인하고...
            for (int i=0; i<4; i++) {
                point next = {cur.x + dx[i], cur.y + dy[i]};
                //안 익은 토마토라면 큐에 push한다.
                if (tomato[next.y][next.x] == 0) {
                    //tomato[next.y][next.x] = 1;
                    q.push(next);
                }
           }
      }
 }

이렇게 된다면 우리는 queue에서 꺼낼 때 확인을 한다. 이렇게 된다면 메모리 초과가 될 것이다. 왜그럴까?

왜냐하면 같은 곳이 중복해서 들어갈 수 있기 때문이다. 내가 만약 (2, 2)를 가고 싶다고 하는데 큐에 (1, 2), (2, 1)이 있다고 해보자. 그러면 (2, 2) 큐에 있는 (1, 2), (2, 1)에 대해서 둘 다 (2, 2)가 큐에 들어가게 된다. 이렇게 100번만 지나면 2^100개가 넘어가는 중복된 값이 큐에 들어가게 된다. 메모리가 터지는 것은 당연할 것이다.

우리는 이렇게 BFS를 할 때는 확인을 어떻게, 언제 해줘야 중복 확인을 안 하는지 언제나 생각을 하면서 코드를 짜야할 것이다.