[BOJ] C++ 7576 토마토 - 시작점이 여러 개인 최단 경로, BFS

7576번: 토마토

예제

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

ans : 8

---

최단 경로를 보고 바로 BFS를 떠올렸다. 조금 다른 점은 토마토가 여러 개인 경우 동시에 여러 시작점에서 BFS를 시작해야 한다는 것이다. 토마토들 간의 우선순위는 없으니 간단하게 큐에 시작점을 모두 넣고 BFS를 돌리면 된다.

 

구현은 전에 푼 문제와 거의 똑같다. 조금 다른건 토마토가 없는 칸, 즉 다른 문제의 벽에 해당하는 칸만 0으로 초기화하고 이미 방문한 것과 똑같이 처리해서 조금 최적화할 수 있었다. 이런 사소한 최적화들이 유용한 잡기술이 되기도 한다.

/** BFS 7576 토마토 **/
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#define MAX 1001
using namespace std;

int board[MAX][MAX];
int dist[MAX][MAX];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m; // n행 m열

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

    queue<pair<int, int>> Q;
    cin >> m >> n;
    for (int i = 0; i < n; i++)
    {
        fill(board[i], board[i] + m, 0);
        fill(dist[i], dist[i] + m, 0);
    }

    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(make_pair(i, j));
            }
            if (board[i][j] == 0)
            {
                // 토마토가 없는 칸은 0으로 그냥 둬서 이미 방문한것과 같게 처리한다.
                dist[i][j] = -1;
            }
        }

    while (!Q.empty())
    {
        pair<int, int> cur = Q.front();
        Q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            //(nx, ny)는 cur의 상하좌우 칸이다.
            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if (dist[nx][ny] >= 0)
                continue;
            dist[nx][ny] = dist[cur.first][cur.second] + 1;
            Q.push(make_pair(nx, ny));
        }
    }

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