백준 7576 - 토마토 - BFS

문제

문제링크 : https://www.acmicpc.net/problem/7576

풀이전략

1. 익은 토마토의 가로세로 부분만 영향을 받는다. 1은 익은 토마토, 0은 익지않은 토마토, -1은 빈칸이다.
2. BFS로 순차적으로 계산하여 마지막으로 남는 토마토의 시간을 계산해주면 그 값이 최소날짜이다. 단 queue가 비었는데도 불구하고 익지 않은 토마토가 남아있으면 이때는 토마토가 익지 못하는 상황이다.
3. base case : 모든 토마토가 익지는 못하는 상황이라면 -1을 출력한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N, M;
// 토마토의 위치를 저장하는 배열
int a[1002][1002];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

// 토마토의 관한 struct
// r은 행, c는 열, val은 토마토가 익은 시간
struct Tomato{
    int r, c, val;
    // 습관대로 a, b, c 써서 틀려버림 변수이름 집중하기
    // Tomato(int a, int b, int c){
    Tomato(int z, int x, int v){
        r = z;
        c = x;
        val = v;
    }
};
int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    memset(a, -1, sizeof(a));
    cin >> M >> N;

    queue<Tomato> tom;

    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            cin >> a[i][j]; 
            /// 익은 토마토의 경우 queue에 넣어준다.
            if(a[i][j] == 1){
                tom.push(Tomato(i, j, 1));    
            }
        }
    }
    
    
    //익은 토마토를 기준으로 BFS를 시작한다. 
    while(!tom.empty()){
        Tomato k = tom.front();
        tom.pop();
        for(int i=0; i<4; i++){
            int rr = k.r + dy[i];
            int cc = k.c + dx[i];
            if(a[rr][cc] == 0){
                // 토마토를 익게만들고, 그 익은 시간을 배열에 넣어준다.
                a[rr][cc] = k.val+1;
                // cout<<rr<<" "<<cc<<" "<<a[rr][cc]<<endl;
                // 시간을 1증가시킨 뒤 queue에 넣어주어 BFS를 계속한다.
                tom.push(Tomato(rr,cc,k.val+1));
            }
        }
    }
    int res = -1;
    // BFS가 끝나면 전체 토마토를 확인하여 최대 시간을 구한다. 
    // 단 토마토가 하나라도 익지 않았을 경우 -1을 출력한다. 
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(a[i][j] > res) res = a[i][j];
            if(a[i][j] == 0){
                res = 0;
                break;
            }
        }
        if(res == 0) break;
    }
    cout<< res-1<<endl;
    return 0;
}

소감

문제는 익은토마토를 큐에 넣어주며 잘 풀었지만 처음에 struct를 선언할 때, 배열에서 선언한 변수인 a를 습관적으로 그냥 써버렸다. 앞으로는 스트럭트에서 처리할 때는 aa, bb, cc 등 사용하지 않을 변수의 이름으로 처리해야겠다.