토마토

문제: 토마토 (백준 7576번)

구조 분석

이는 전형적인 BFS 문제이다. 익은 토마토부터 가까운 토마토를 방문하며 expand 시키며 모든 토마토가 익을 때까지 걸리는 날짜를 세면 된다.

풀이 방법

BFS로 문제를 풀면 된다. 특이하게 어려운 점은 없다.

코드

#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;

int n, m;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int box[1000][1000];
int visited[1000][1000];

int check() {
    int flag = 1;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (box[i][j] == 0) flag = 0;
        }
    }
    return flag;
}

void bfs() {
    int cnt = 0;
    queue<pair<pair<int,int>,int>> Q;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (box[i][j] == 1) {
                Q.push(make_pair(make_pair(i,j),0));
            }
        }
    }
    while(!Q.empty()) {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int c = Q.front().second;
        cnt = c;
        c++;
        Q.pop();
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0<=nx && nx<n && 0<=ny && ny<m) {
                if (box[nx][ny]==0 && visited[nx][ny]==0) {
                    box[nx][ny] = 1;
                    visited[nx][ny] = 1;
                    Q.push(make_pair(make_pair(nx,ny),c));
                }
            }
        }
    }
    if (check()) {
        cout << cnt << "\n";
    }
    else {
        cout << -1 << "\n";
    }
}

int main() {
    cin >> m >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> box[i][j];
        }
    }
    if (check()) {
        cout << 0 << "\n";
    }
    else {
        bfs();
    }
    return 0;
}  

정리

전형적인 BFS 문제였다. 이제 이러한 유형의 BFS는 익숙해졌다.