[BaekJoon] 7576번 : 토마토

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• 시작점이 여러 개 있는 BFS 문제로 BFS에 대한 특징이 제대로 있어야 합니다.
• BFS는 큐에 처음 시작점을 한 개 담았다면, 이 문제는 시작점이 여러 개 있으면 여러 개를 하나의 큐에 담기만 하면 됩니다.
• 큐에서 front에 해당되는 시작점에서 BFS를 진행하게 되고 특정 영역은 여러 시작점 중 처음 방문할 때가 최단 거리입니다.

#include<iostream>
#include<utility>
#include<queue>
using namespace std;

int n,m;
int arr[1000][1000];
int dist[1000][1000];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

bool inside(int y, int x){
    return 0<=y && y<n && 0<=x && x<m;
}

int main(){
    cin>>m>>n;
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
            if(arr[i][j] == 1){
                dist[i][j] = 1;
                q.push({i,j});
            }
        }
    }
    
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for(int i=0;i<4;i++){
            int dy = y + dir[i][0];
            int dx = x + dir[i][1];
            
            if(inside(dy,dx) && arr[dy][dx] == 0 && !dist[dy][dx]){
                dist[dy][dx] = dist[y][x]+1;
                q.push({dy,dx});
            }
        }
    }
    
    int ans = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j] != -1 && dist[i][j] == 0){
                cout<<-1;
                return 0;
            }
            ans = max(ans, dist[i][j]);
        }
    }
    cout<<ans-1;
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.