BOJ 7576 토마토

boj 7576 토마토

BFS로 풀 수 있는 문제다. 조금 독특한 점은 시작점이 여러 곳이 될 수 있다는 것이다. 전체를 다 돌아보고 시작점이 될 수 있는 곳을 다 찾아 한번씩 bfs를 다 돌려보는 풀이가 가장 먼저 생각났지만, 최대 시간복잡도가 O((NM)^2)이 될 수 있어 이 방법으론 풀 수 없다. 그래서 토마토 정보를 입력받을 때, 익은 토마토의 시작점을 전부 큐에 넣어주고 bfs를 돌리는 방식으로 문제를 풀었다. 익은 토마토의 경우 거리 dis 값이 전역변수이니 0으로 채워지고, 안 익은 토마토는 dis 값을 -1로 둔다. 코드를 한번 보자.

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int n, m;
int board[1005][1005];
int dis[1005][1005];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue <pair<int, int>> q;
    cin >> m >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 1) q.push({ i,j });
            if (board[i][j] == 0) dis[i][j] = -1;
        }
    }

    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (dis[nx][ny] >= 0) continue;
            dis[nx][ny] = dis[cur.first][cur.second] + 1;
            q.push({ nx,ny });
        }
    }

    int ans = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (dis[i][j] == -1)
            {
                cout << -1;
                return 0;
            }
            ans = max(ans, dis[i][j]);
        }
    }

    cout << ans;
}

while문을 한번 돌 때마다 시작점으로부터 거리가 1씩 증가한다는 것을 생각하면 while문 안에서 dis배열을 왜 저렇게 처리했는지 이해할 수 있다. 마지막에 bfs를 돌고도 안익은 경우가 한개라도 있을 경우 문제의 조건에 따라 -1을 출력한다.