[백준] 토마토 7576번 (c++)

출처 : 7576번: 토마토 (acmicpc.net)

7576번: 토마토

풀이 방법

익은 토마토의 인접한 토마토들이 익어가는 것으로 보아 그래프 문제이다.

인접한 단계에 따라 기간이 흘러가므로 bfs문제로 볼 수 있다.

그런데 이 문제는 bfs의 시작점 즉 처음부터 익어있는 토마토가 한 개가 아니므로 시작점을 여러개 해주어야한다.

그러기 위해 입력을 받을 때 처음으로 익어 있는 토마토의 위치를 저장해 둔다.

그리고 bfs를 돌기위해 저장해둔 토마토 위치를 모두 큐에 넣어 주고 bfs를 실행한다.

bfs를 실행할때 각 위치의 값은 이전 값 + 1로 설정해두어 하루가 지났음을 기록한다.

bfs를 수행한후 각 좌표를 돌아보며 만약 익지 않은 토마토가 존재하면 cout << - 1 을 해주고 프로그램을 종료한다

익지 않은 토마토가 없으면 배열에서 가장 큰 값을 선택해서 그 값에 -1 한 값을 출력해 준다.

-1을 하는 이유는 처음 익은 토마토의 좌표의 배열값이 0으로 시작한게 아니라 1로 시작했기 때문에 1을 빼준다.

#include <bits/stdc++.h>

using namespace std;

int M,N;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
vector<vector<int>> board;
vector<pair<int, int>> tomato;
int visited[1001][1001];
int ans = 0;
void bfs() {
    queue<pair<int, int>> q;
    for (int i = 0;i < tomato.size();i++) { // 초기 익은 토마토 위치 큐에 저장
        q.push(tomato[i]);
        visited[tomato[i].first][tomato[i].second];
    }
    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for (int i = 0;i < 4;i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny >= 0 && nx >=0 && ny < N && nx < M) {
                if (board[ny][nx] == 0) {
                    visited[ny][nx] = 1;
                    board[ny][nx] = board[y][x] + 1;
                    q.push(make_pair(ny, nx));
                }
            }
        }
    }

}
int main() {
    cin >> M >> N;
    board.resize(N);
    memset(visited, 0, sizeof(visited));
    for (int i = 0;i <N;i++) {
        board[i].resize(M);
        for (int k = 0; k < M;k++) {
            cin >> board[i][k];
            if (board[i][k] == 1) {
                tomato.push_back(make_pair(i, k));
            }
        }
    }

    bfs();
    for(int i = 0;i < N;i++) {
        for (int k = 0;k < M;k++) {
            if (ans < board[i][k]) { // 가장 큰 수 찾기
                ans = board[i][k];
            }
            if (board[i][k] == 0){ // 익지 않은 토마토가 있는 경우
                cout << -1;
                return 0;
            }
        }
    }
    cout << ans-1;
    return 0;
}