[C++] 백준 7576번 토마토

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

풀이

익은 토마토 칸은 1칸, 익지 않은 토마토 칸은 0칸, 빈 칸은 -1칸이라고 하자.

이 문제는 모든 1칸에서부터 가능할 때까지 상하좌우 인접 칸을 1로 만들어야 하므로 BFS로 풀었다.

큐에는 모든 1칸의 좌표를 넣고, dist 배열에는 어떤 칸과 그 칸의 시작 1칸 사이의 거리를 저장한다.

• 처음 1칸들은 dist = 0
• 1칸(prev)에 인접한 0칸(next)들은 dist(next) = dist(prev) + 1

최종적으로 출력해야 하는, 토마토가 모두 익을 때까지의 최소 날짜 ans를 구하기 위해

• 입력받을 때 0칸의 개수를 left에 저장
• 0칸이 1칸이 될 때마다 left 1씩 감소
• 최종 left 값이 0이 아니면, 토마토가 모두 익지는 못하였으므로 ans = -1
• 최종 left 값이 0이면, ans = dist 배열의 최대값

코드

#include <bits/stdc++.h>
using namespace std;

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

    int N, M;
    cin >> M >> N;
    vector<vector<int>> box(N, vector<int>(M));

    int left = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> box[i][j];
            if(box[i][j] == 0) left++;
        }
    }

    int ans = 0;
    vector<vector<int>> dist(N, vector<int>(M, -1));
    queue<pair<int, int>> q;

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(box[i][j] == 1) {
                q.push({i, j});
                dist[i][j] = 0;
            }
        }
    }

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    while(!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if(box[nx][ny] != 0) continue;
            if(dist[nx][ny] != -1) continue;

            
            box[nx][ny] = 1;
            left--;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});

            ans = max(ans, dist[nx][ny]);
        }
    }

    if(left != 0) ans = -1;

    cout << ans;
    return 0;
}

시간복잡도

노드의 수는 N×M, 간선의 수는 최대 4×N×M 이므로
이 풀이의 시간복잡도는 O(NM) 이다.