이번 문제는 BFS 알고리즘을 활용하여 해결하는 문제였다. DFS & BFS

• 원래 BFS는 방문 처리를 하였지만 이번 문제에서는 그래프에 직접적으로 값을 더하여 그 중 가장 큰 값을 시간으로 구했다.
• 그래프 좌표의 이동을 dx, dy 배열로 구현했다.
• BFS를 통해 그래프 전체를 탐색하며 값을 업데이트 한 후, 만약 그래프에 0이 남아있다면 -1을 출력하였다.

Code

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 1001
using namespace std;

int m,n, k;
int result=0;
int graph[MAX][MAX];
queue<pair<int, int>> tomato;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool success=true;

void Input(){
    cin>>m>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>graph[i][j];
            if(graph[i][j]==1){
                tomato.push(make_pair(i, j));
            }
        }
    }
}

void BFS(){
    while(!tomato.empty()){
        int y=tomato.front().first;
        int x=tomato.front().second;
        tomato.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)&&graph[ny][nx]==0){
                graph[ny][nx]=graph[y][x]+1;
                tomato.push(make_pair(ny, nx));
            }
        }
    }
}

int Solution(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(graph[i][j]==0){
                success=false;
            }
            if(result<graph[i][j]){
                result=graph[i][j];
            }
        }
    }
    if(!success)
        return -1;
    else
        return result-1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    BFS();
    cout<<Solution()<<endl;
    return 0;
}