[C++] 백준 7576번 문제풀이

이 문제를 보고 2차원 하루 지났을 때 토마토가 어떻게 퍼지는지 보았는데

입력이 

6 4

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 1 

일 때 .

Day 1

0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	1
0	0	0	0	1	1

Day 2

0	0	0	0	0	0
0	0	0	0	0	1
0	0	0	0	1	1
0	0	0	1	1	1

 

Day 3

0	0	0	0	0	1
0	0	0	0	1	1
0	0	0	1	1	1
0	0	1	1	1	1

이런식으로 BFS 를 써야 될거 같이 생겼다. 

좌표를 하나의 node 라고 생각하면 근처의 node 들을 방문한뒤 다음 node 의 근처 node들을 방문 하는 식이다.

BFS 를 좌표로 표현하기 위해 pair<int.int> 를 사용하여 x축 , y축을 표현하였고

#include <iostream>
#include <queue>
using namespace std;
 
int arr[1001][1001];
int M, N;
 
queue<pair<int, int>> q;
 
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
 
void bfs(void){
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx <= 0 || nx > N || ny <= 0 || ny > M) continue;
            if(arr[nx][ny] == 0){
                arr[nx][ny] = arr[x][y] + 1;// 1을 가지고 있는 좌표 주변에 +1을 더한다.
                q.push(make_pair(nx, ny));
            }
        }
    }
}
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> M >> N;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> arr[i][j];
            if(arr[i][j] == 1)
                q.push(make_pair(i, j));
        }
    }
    
    bfs();
    
    int max = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(arr[i][j] == 0){
                cout << "-1" << '\n';
                return 0;
            }
            
            if(max < arr[i][j])
                max = arr[i][j];
        }
    }
    cout << max - 1 << '\n';
    
    return 0;
}