[C++] 백준 7576번: 토마토

문제

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

7576번: 토마토

풀이

 

입력을 열, 행으로 받기 때문에 문제를 꼼꼼히 읽지 않으면 틀리기 쉽다.

 

1. 입력받을 때 익은 토마토가 있는 좌표를 queue에 입력한다.
   • 0, 0부터 익은 토마토를 BFS 탐색해버리면 익은 토마토가 여러 개 있을 때, 중복 방문할 가능성이 있다.
2. BFS로 익지 않은 토마토가 있는 곳을 탐색한다.
   이 때, queue에서 꺼낸 좌표의 토마토의 최소 일수 + 1 해준다.
   
   
3. 결과를 출력할 때, 아직 익지 않은 토마토가 있는지 반드시 확인한다.
   이 과정을 해주지 않아 틀렸습니다. 를 보았는데 아래 반례로 찾아냈다.
   
   

3 3
1 0 0 
-1 -1 -1 
0 0 0 
// 정답: -1

소스

#include <iostream>
#include <queue>
#define MAX 1001
 
int M, N;
int tomatoes[MAX][MAX];
 
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
bool isValid(int a, int b)
{
    if(a>=N || b>=M || a<0 || b<0)
        return false;
    return true;
}
 
bool isDone()
{
    for(int i=0; i<N; ++i) {
        for(int j=0; j<M; ++j){
            if(tomatoes[i][j] == 0)
            {
                return false;
            }
        }
    }
    return true;
}
 
int main()
{
    std::queue<std::pair<int, int>> q;
    
    std::cin >> M >> N;
    for(int i=0; i<N; ++i) {
        for(int j=0; j<M; ++j){
            std::cin >> tomatoes[i][j];
            if(tomatoes[i][j] == 1)
                q.push(std::make_pair(i, j));
        }
    }
    
        
    int days = 0;
    while (!q.empty())
    {
        int qSize = q.size();
        while(qSize--)
        {
            int nowX = q.front().first;
            int nowY = q.front().second;
            q.pop();
            
            for(int i=0; i<4; ++i)
            {
                int x = nowX + dx[i];
                int y = nowY + dy[i];
 
                if(isValid(x, y) && (tomatoes[x][y] == 0))
                {
                    q.push(std::make_pair(x, y));
                    tomatoes[x][y] = tomatoes[nowX][nowY] + 1;
                }
            }
        }
        ++days;
    }
    
    std::cout << (isDone() ? days-1 : -1);
    
    return 0;
}