백준) 7576 토마토

7576. 토마토

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

1. 접근

익은 토마토는 주변의 익지 않은 토마토를 전염시켜 익게 만든다.

주변이란 위, 아래, 왼쪽, 오른쪽의 사방향을 말하며, 익은 토마토의 전파는 하루가 걸린다.

맵의 모든 토마토를 익게 만드려면 몇 일이 걸릴까?

실제로 익어가는 과정을 시뮬레이션해보면 알 수 있다.

다만 익은 토마토를 기록해주고 전파되는 과정을 구현하고, 동시에 모든 토마토가 익었는지 확인하는 구현도 필요한데,

마침 BFS는 매우 유사한 구조를 띄고 있다.

익은 토마토를 기점으로 전파하는 방법은, 노드를 방문해나가는 과정과 비슷하며,

익은 토마토를 다시는 확인할 필요가 없는 구현은, visit을 체크하면서 다시 방문하지 않는 과정과 같기 때문이다.

2. 풀이

먼저 0일차의 익은 토마토의 좌표들을 큐에 저장한다. 1일차로 나아갈려면 어떻게 해야할까?

BFS의 특성상 진행할 수 있으면 다시 큐에 들어가야 하므로, 일자를 기록할려면 0일차의 토마토 갯수만큼 큐질을 해야한다.

따라서 큐의 사이즈만큼(X일차에 새롭게 익은 토마토 갯수)만 큐질을 하면 일자를 기억하면서도 큐질을 할 수 있다.

또한 0인 토마토를 1로 익게 만들고 나서 0인 토마토가 더이상 없으면 탈출조건으로 잡을 수 있다.

이렇게 하면 온갖 큐질 이후에도 0인 토마토가 남는 상황도 체크할 수 있다.

3. 코드

#include <stdio.h>
#include <queue>
using namespace std;
 
int tomato[1000][1000], visit[1000][1000], m, n;
int dir[4][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
int cnt, size, x, y, xx, yy;
 
struct col {
    int x, y;
};
queue<col> que;
 
int bfs() {
    int ans = 1;
    while (!que.empty()) {
        int size = que.size();
        for (int i = 0; i < size; ++i) {
            col c1 = que.front();
            que.pop();
            x = c1.x, y = c1.y;
 
            if (visit[x][y])
                continue;
            else
                visit[x][y] = 1;
 
            for (int j = 0; j < 4; ++j) {
                xx = x + dir[j][0];
                yy = y + dir[j][1];
 
                if (xx < 0 || xx >= n || yy < 0 || yy >= m)
                    continue;
                else if (tomato[xx][yy] == -1)
                    continue;
 
                else if (tomato[xx][yy] == 0) {
                    que.push({ xx,yy });
                    tomato[xx][yy] = 1;
                    cnt--;
                }
 
                if (cnt == 0)
                    return ans;
            }
        }
        ans++;
    }
    return -1;
}
 
int main() {
    scanf("%d %d", &m, &n);
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &tomato[i][j]);
 
            if (tomato[i][j] == 1)
                que.push({ i,j });
            else if (tomato[i][j] == 0)
                cnt++;
        }
    }
    printf("%d", bfs());
 
    return 0;
}

사실 visit 배열을 따로 쓰지 않아도 BFS질을 할 수 있긴 하다.