[C++] 백준 7576 - 토마토

백준 7576 : 토마토
난이도 : 골드 5

시간 : 50분 소요

 

 

문제

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

풀이 과정

 

어떤 식으로 풀어야 할지는 금방 생각했지만 구현하는 것이 오래걸렸다.

 

해결 방법은 먼저 시작점(익은 토마토)를 순차적으로 찾은 후, 시작점에서 익힐 수 있는 토마토들을 큐에 넣는다.

그 후 큐가 비어질 때까지 큐에 있는 모든 토마토를 방문하면 된다.

 

x, y 좌표와 날짜를 저장하는 자료형이 필요했지만 내가 알고 있는 자료형은 pair 뿐이라 어떻게 구현할지 고민을 했다.

 

그래서 생각한 방법은 먼저 pair 자료형으로 x, y 좌표를 큐에 넣는다.

날짜를 저장하는 것은 num[1001][1001] 이라는 2차원 배열을 새로 만들어 좌표마다 익는 날짜를 저장하도록 하였다.

또한, 현재 토마토에서 상하좌우로 익힐 수 있는 토마토가 있을 때 큐에 넣는 동시에 현재 토마토 날짜에 +1를 했다.

 

모든 토마토 방문이 끝나면 num 배열에서 가장 큰 수가 토마토가 모두 익을 때까지의 최소 날짜가 된다.

이외에도 예외처리도 고려해야 해서 시간이 좀 걸렸다.

 

 

최종 코드

#include <iostream>
#include <queue>

using namespace::std;

int M, N;
int tmt[1001][1001];
int num[1001][1001];

int ud[4] = {-1,1,0,0};
int lr[4] = {0,0,-1,1};

queue<pair<int, int>> q;


void bfs(int y, int x){
   
    for(int i=0; i<4; i++){
        int ny = y+ud[i];
        int nx = x+lr[i];
        tmt[y][x] = 1;
        
        if(ny>=0 && nx>=0 && ny<N && nx<M){
            if(tmt[ny][nx] == 0 && num[ny][nx] == 0){
                q.push({ny, nx});
                num[ny][nx] = num[y][x] + 1;
            }
        }
    }
    
}

int main(){
    scanf("%d %d", &M, &N);
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            scanf("%d", &tmt[i][j]);
        }
    }
    int t1 = 0;
    
     for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(tmt[i][j] == 1){
                num[i][j] = 0;
                bfs(i, j);
            }else if(tmt[i][j] == 0){
                t1++;
            }
        }
    }
    
    if(t1 == 0){
        printf("0\n");
        return 0;
    }
    
    while(!q.empty()){
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        bfs(ty,tx);
        
    }
    
    int result = 0;
    for(int i=0; i<N; i++){
       for(int j=0; j<M; j++){
           if(result<num[i][j])
               result = num[i][j];
           else if(tmt[i][j] == 0){
               printf("-1\n");
               return 0;
           }
               
       }
   }
    
    printf("%d\n", result);
    
    
}