[BOJ_C++] 7576번: 토마토

CODE

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[1002][1002];
int dist[1002][1002];
int n, m, day;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

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

    cin >> m >> n;
    queue<pair<int, int>> q;
    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) dist[i][j] = -1;
        }
    }

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

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

    cout << day;

    return 0;
}

풀이

1. m과 n을 입력받는다. (m이 가로 칸으 수인 것을 주의!)
2. 시작점이 여러개이므로 모든 시작점을 큐에 넣고 bfs 탐색을 시작해야 한다.
3. 토마토가 익는데 걸리는 시간은 토마토사이의 거리와 동일하다는 것을 생각하고 문제를 해결해야 한다.
   1. 이미 익거나 토마토가 들어있지 않은 칸은 0으로 익지 않은 토마토는 -1로 초기화
4. 탐색을 하며 거리를 갱신해주고 답을 출력하기 전에 익지 않은 토마토(-1)가 있는지 확인하고 있다면 -1을 없다면 가장 큰 값을 출력한다.

결과