• 입력 : 세로 크기 N, 가로 크기 M ( 2 <= M,N <= 1,000 )

    • 1 = 익은 토마토
    • 0 = 익지 않은 토마토
    • -1 = 토마토가 들어있지 않은 칸

  • 출력 : 토마토가 모두 익을 때까지의 최소 날짜 출력

    • 저장될 때부터 모든 토마토가 익었다면 0
    • 모두 익지 못하는 상황이면 -1

문제 해결

  • 입력을 받으면서 익은토마토의 위치를 큐에 PUSH하고 (BFS를사용), 안 익은 토마토의 갯수를 저장한다.

    • 안익은 토마토가 없다면 모두 익은것이므로 0을 출력하고 끝낸다.
    • 아니라면 큐를 이용하여 BFS를 시작한다.

  • day를 기록하기위해 큐에 들어간 사이즈만큼 탐색을 해야한다.

  • BFS의 조건 ( 토마토가 들어있지않은곳, 맵 밖 벗어난곳 ) 을 생각하여 큐에 넣는다.

  • 큐 사이즈만큼 POP이 끝났으면 하루가 지난것이므로 day를 증가

  • 큐가 비어있을때까지 반복한다.

 

Code

#include <iostream>
#include <queue>
using namespace std;
typedef struct coordinate
{
    int x;
    int y;
};
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
int m, n; // 가로m 세로n
int map[1000][1000];
int visit[1000][1000];
 
int tomato_count;
queue<coordinate> qu;
 
int day = -1;
 
void input()
{
    cin >> m >>n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 1)
                qu.push({ i,j });   // 익은 토마토의 자리는 큐에 넣어준다.
            else if (map[i][j] == 0)
                tomato_count++;     // 안익은 토마토의 갯수를 카운트한다.
        }
}
 
void bfs()
{
    // tomato_count 가 모두 소진됐다면 토마토가 모두 익은것
    // tomato_count 가 남아있다면 ( 0 이상 ) 토마토가 익지 못하는 상황 -> -1 출력
 
    while (!qu.empty()) // 큐가 공백이 될때까지 반복한다
    {
        int queue_size = qu.size(); // 큐 사이즈 변수.. 큐 사이즈만큼 pop을 돌리고 day를 카운트
 
        for (int i = 0; i < queue_size; i++)
        {
            coordinate temp = qu.front(); // 큐의 최하단 원소 빼내어 변수에 저장
            qu.pop();
 
            // 이미 bfs를 통해 방문했던 곳이라면 패스, 아니면 visit 배열에 체크
            if (visit[temp.x][temp.y])
                continue;
            else
                visit[temp.x][temp.y] = 1;
 
            // 맵 경계선, 토마토가 들어있지않은곳 검사하여 사방좌표를 큐에 넣어준다.
            for (int j = 0; j < 4; j++)
            {
                int x = temp.x + dx[j];
                int y = temp.y + dy[j];
 
                if (x < 0 || x >= n || y < 0 || y >= m)
                    continue;
                else if (map[x][y] == -1)
                    continue;
                else if (map[x][y] == 0)
                {
                    qu.push({ x,y });
                    map[x][y] = 1;
                    tomato_count--;
                }
            }
        }
        // 큐 사이즈만큼 돌렸으면 day 하나 증가시킨다.
        day++;
    }
    // 안익은 토마토가 남아있다면,,
    if (tomato_count > 0)
        day = -1;
}
 
int main()
{
    input();
 
    // 안익은 토마토가 없다면 모두 익은것이므로 0 출력
    if (tomato_count == 0)
        day = 0;
    else
        bfs();
 
    cout << day;
    return 0;
}