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

문제: www.acmicpc.net/problem/7576

7576번: 토마토

 

 

문제풀이

 

BFS를 이용해 최단거리를 구하는 문제이다.

 

이 문제는 시작점(익은 토마토)이 여러 곳이므로 시작점을 모두 큐에 넣어준다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int board[1000][1000];
int dist[1000][1000];

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

    int m,n;
    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) //익지 않은 토마토는 -1
                dist[i][j] = -1;
        }
    }
    //빈 공간의 dist값은 모두 0이다. (전역으로 선언)

    while(!q.empty()){
        pair<int,int> cur = q.front();
        q.pop();

        for(int dir=0; dir<4; dir++){
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(dist[nx][ny] >= 0) continue;

            dist[nx][ny] = dist[cur.first][cur.second] + 1;
            q.push({nx,ny});
        }

    }

    int day=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(dist[i][j] == -1){ //익지 않은 토마토가 있다면 -1 출력
                cout<<-1;
                return 0;
            }
            day = max(day, dist[i][j]); 
            //dist의 값 중 가장 큰 값이 토마토가 모두 익는데 걸린 일수이다.
        }
    }

    cout<<day;

    return 0;
}

 

 

결과