백준 7576 토마토

bfs를 통해 최소 비용을 구하는 문제다.

하루가 지나면 익는다고 했으므로, 가중치가 1이라고 할 수 있다.

 

토마토가 없는 곳과 마지막에 답을 출력하는 조건을 조심해야 한다.

 

자세한 설명은 아래 주석으로..

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
int n, m, ans;
int maze[1000][1000];
int visit[1000][1000];
 
int dr[4] = { -1, 0, 1,  0 };
int dc[4] = {  0, 1, 0, -1 };
 
void bfs(queue<pair<int,int>> q) {
    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];
            //배열 안에 들어가는지 검사
            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                //익지 않은 토마토인지 검사
                if (visit[nr][nc] == 0 && maze[nr][nc] == 0) {
                    visit[nr][nc] = visit[row][col] + 1;
                    q.push(make_pair(nr, nc));
                    //거리를 계속 갱신
                    if (ans < visit[nr][nc])ans = visit[nr][nc];
                }
            }
        }
    }
}
 
int main(int argc, char** argv) {
    queue<pair<int, int>> q;
    cin >> m >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &maze[i][j]);
            //익은 토마토가 있으면, visit에 check하고, q에 바로 넣는다.
 //처음에 1로 시작하도록 한다. 나중에 출력을 0과 구별해주기 위해서
            if (maze[i][j] == 1) {
                visit[i][j] = 1;
                q.push(make_pair(i, j));
            }
        }
    }
 
    bfs(q);
 
    //거리가 갱신되지 않았다면 익은 토마토가 없으므로 0출력.
    if (ans == 0)printf("0\n");
    else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //익을 수 없는 토마토가 있는지 검사한다. 없으면 -1 출력 후 종료.
                //토마토가 없는 곳도 조건을 따져봐야 한다.(-1인 곳)
                if (visit[i][j] == 0 && maze[i][j] != -1) {
                    printf("-1\n");
                    return 0;
                }
            }
        }
        printf("%d\n", ans - 1);
    }
 
    return 0;
}