JArchive 프로그래밍 일기

문제

토마토 백준 7576번

리뷰

토마토가 최소 몇 일이 지나야 다 익을 수 있는지 출력하는 문제다.

익은 토마토가 1개로 시작하는 줄 착각하고서 헤맸다. 진짜... 문제를 정독해야겠다.

시작점이 반드시 하나라고 생각해서 1시간 동안 붙잡고있었는데 계속 틀렸다.

시작점을 큐에 push 하고 시작하고나서야 맞출 수 있었다.

처음에 토마토 값들을 (0 , -1, 1 ) 입력받을 때, 1이면 이미 익은 것이니까 이 지점들을 시작으로 상하좌우가 익어간다.

그래서 큐에 BFS 시작점으로써 넣어준다.

boundary 함수는 M * N 상자 범위를 벗어나는지 여부를 1 / 0 으로 알려준다.

큐에서 하나씩 꺼내서 상하좌우를 살피는데, 범위 안에 있고 아직 안익었다면( 0이라면 ) ripe 익혔다고 세준다.

그리고 만약 day 가 증가됬다면 갱신해준다.

day를 그냥 출력하면 맞출 줄 알았는데, 처음에 시작점은 이미 값을 1로 갖고 있으니까, 하루가 지나도 2가 되버린다.

M * N 크기의 A 배열이 어떻게 변해가는지 출력해보면서 발견했다.

그래서 마지막에 day - 1 을 해준다.

코드

#include <iostream> 
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1000+1 

using namespace std;

int M, N; // 가로, 세로 
int A[MAX][MAX];
int zero_cnt, ripe, day;

queue<pair<int,int> > q;

// 상 하 좌 우
int diff_x[4] = {-1, 1, 0, 0};  // N  
int diff_y[4] = {0, 0, -1, 1};  // M


bool boundary(int x, int y){ // M * N 범위 초과 하는지 확인 
    bool res = (x < N && x >= 0 && y < M && y >= 0) ? 1 : 0;
    return res;
}

void BFS(){

    while(!q.empty()){

        pair<int,int> now = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++){ // 상하좌우 확인 

            int x = now.first + diff_x[i];
            int y = now.second + diff_y[i];

            if(boundary(x, y) && A[x][y] == 0){ // 범위 안에 있고, 안 익었으면. 
                A[x][y] = A[now.first][now.second] + 1; 
                q.push(make_pair(x, y));
                ripe++; // 익은 개수 
                day = max(A[x][y], day); // day 증가됬다면 갱신 
            }
        }

    }

    if(zero_cnt > ripe) { // 모두 익지 못한다. 
        cout << -1; 
    }else{
        cout << day-1;
    }

}

int main(void){

    cin >> M >> N; // 가로, 세로  

    for(int i = 0; i < N; i++){ // 세로 N

        for(int j = 0; j < M; j++){ // 가로 M 

            scanf("%d", &A[i][j]);
            if(A[i][j] == 0) zero_cnt++; // 안익은 토마토 개수 센다  
            else if(A[i][j] == 1) {
                q.push(make_pair(i, j)); // 가능한 시작점 모두 넣는다  
            }
        } 
    } // 입력받기 끝

    if(zero_cnt == 0) cout << 0; // 저장될 때부터 모든 토마토가 익어있는 상태
    else{ // 탐색시작 
        BFS(); 
    }

    return 0;    
}