[c++/알고리즘] 백준 7576 토마토 : BFS

• 문제 이해 :
  1. 가중치가 모두 같은 경로를 탐색하며 , 최소 일수를 구하는 것이기 때문 -> BFS로 풀이한다.
  2. 상자의 크기는 M*N // 문제를 똑바로 안읽고 의식의 흐름에 따라 N*M으로 입력받아서.. 시간이 걸렸다.

내가 작성한 코드

#include <iostream>
#include <queue>

using namespace std;

int map[1001][1001], ch[1001][1001];

int main(){
    int n, m, a, ck=0, chz = 0 ,x, y, day=0;
    // 앞, 뒤 , 오른, 왼 으로 이동하기 위한 배열
    int dx[4] = {0 , 1, 0 ,-1};
    int dy[4] = {1, 0, -1, 0};
    queue<pair<int, int>> Q;

    cin >> n >> m;

    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            cin >> a;
            map[i][j] = a;
            // 익은 토마토를 모두 queue에 넣는다.
            if(a == 1) {
                Q.push(make_pair(i, j));
                ch[i][j] = 1;
            }
            // 이미 다 익었을 경우를 체크하기 위해 0이 하나라도 존재하는지 체크
            if(a == 0){ chz = 1;}
        }
    }
    // 0 이 존재 하지 않으면 다 익은 것으로 간주하고 0 출력
    if(chz == 0){ cout << 0; return 0;}


    while(!Q.empty()){
        x = Q.front().first;
        y = Q.front().second;
        Q.pop();

        for(int i=0; i<4; i++){
            if(x+dx[i] < 0 || x+dx[i] >= m || y+dy[i]<0 || y+dy[i] >= n) continue;
            
            // 토마토가 익지 않았으며, 이미 지나오지 않은 경우
            if(ch[x+dx[i]][y+dy[i]] == 0 && map[x+dx[i]][y+dy[i]] == 0){
            
                Q.push(make_pair(x+dx[i], y+dy[i]));
                // 인접한 익은 토마토의 일수 + 1
                ch[x+dx[i]][y+dy[i]] = ch[x][y] + 1;
                map[x+dx[i]][y+dy[i]] = 1;
            }
        }
    }
    // 여기까지 토마토가 익을 경우 최대 날짜.

    // map 에 대해 포문돌면서 0 이 있으면(토마토 모두 다 익지 않은 경우) -1 출력
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(map[i][j] == 0 ){ cout << -1; return 0;}
        }
    }
    // 그렇지 않으면 마지막으로 토마토가 익은 날짜에서 원래 익었던 토마토를 하루 센것을 제외해야 하므로 -1하여 출력
    cout << ch[x][y] -1 << endl;
    return 0;
}