#7576번 토마토 (C++)

링크 : www.acmicpc.net/problem/7576

7576번: 토마토

문제의 풀이는 다음과 같다. 

(1) 배열을 2개 만든다. 하나는 값을 입력받을 값(arr), 다른 하나는 방문 여부를 파악하고 동시에 토마토가 익을 날짜를 누적할 배열(check)이다. 

(2) 배열에 값을 넣는다. 이때 check(방문여부를 파악하는 배열)는 모두 -1로 채워넣는다. 

(3) 배열에 입력된 값이 '1'일 경우(즉, 익은 토마토이다), 해당 배열의 쌍을 큐에 넣어주고 check값은 0으로 넣는다. 

(4) 상 / 하 / 좌 / 우로 🍅 가 익을 수 있는 루트를 BFS한다. 만약 해당 위치의 배열값이 '0'이고 (토마토가 아직 안익음), check값이 -1이라면 (방문한 적이 없음을 의미) 해당 값을 큐에 넣어준다. 

(5) 동시에 해당 값의 check배열에 이전 값의 + 1을 해주어 넣는다. 즉, 이전 값보다 하루가 누적되어 토마토가 익었음을 의미한다. 

(6) for문을 돌려서 가장 큰 값의 check를 출력하면 된다.

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int m = 0, n = 0, ans = 0;
int arr[1001][1001];
int ch[1001][1001];
int my[4] = {1,0,-1,0};
int mx[4] = {0,1,0,-1};

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

    cin >> m >> n; // m 가로 n 세로
    queue<pair<int,int>> q;
    int y = 0, x = 0, ny = 0, nx = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> arr[i][j];
            ch[i][j] = -1;
            if(arr[i][j]==1){
                ch[i][j] = 0;
                q.push(make_pair(i,j));
            }
        }
    }
    while(!q.empty()){
        y = q.front().first;
        x = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            ny = y+my[i];
            nx = x+mx[i];
            if(ny>0&&ny<=n&&nx>0&&nx<=m){
                if(arr[ny][nx]==0&&ch[ny][nx]==-1){
                    q.push(make_pair(ny,nx));
                    ch[ny][nx] = ch[y][x] + 1;
                }
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(arr[i][j]==0&&ch[i][j]==-1){
                ans = -1;
                cout << ans << "\n";
                exit(0);
            }
            if(ans<ch[i][j]) ans = ch[i][j];
        }
    }
    cout << ans << "\n";
    return 0;
}