백준 7576 - 토마토

문제

 

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

7576번: 토마토

 

 

풀이

 

BFS 탐색을 이용하는 문제이다. BFS 탐색을 이용해서 같은 레벨에 있는 좌표들의 탐색이 끝나면 그 때 결과 값을 증가시켜주면 된다. 같은 레벨에 있는 모든 좌표를 탐색하고 넘어가는 방법은 큐에 저장된 좌표의 갯수 만큼 반복한 후 넘어가면 된다. 이때 맨 처음 시작하는 좌표가 여러 개 있을 수 있으므로, 그것만 조심하면 된다.

 

1. 전체 배열을 돌면서 1이 있는 좌표를 큐에 저장한다.

2. 큐가 비어있지 않으면 반복

3. 큐의 크기 만큼 반복 (같은 레벨에 있는 모든 좌표를 검사)

4. 큐에서 좌표를 하나씩 꺼내 상하좌우로 검사 후 0이 있는 좌표를 큐에 저장

5. 하루가  지남 (day++)

6. 2, 3, 4, 5 반복

 

 

코드

 

#include <iostream>
#include <queue>
#include <cstring>
 
using namespace std;
 
int M, N;
int graph[1002][1002];
int day = -1;
pair<int, int> pos[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
queue< pair<int,int> > q;
 
void bfs()
{
    while (!q.empty())
    {
        int size = q.size();
 
        while (size--)
        {
            int curX = q.front().first;
            int curY = q.front().second;
            q.pop();
 
            for (int i=0; i<4; i++)
            {
                int nextX = curX + pos[i].first;
                int nextY = curY + pos[i].second;
                if (!graph[nextX][nextY])
                {
                    q.push({nextX, nextY});
                    graph[nextX][nextY] = 1;
                }
            }
        }
        day++;
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> M >> N;
 
    memset(graph, -1, sizeof(graph));
 
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++) cin >> graph[i][j];
 
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            if (graph[i][j] == 1) q.push({i, j});
 
    bfs();
 
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++) 
            if (!graph[i][j])
            {
                cout << -1;
                return 0;
            }
    
    cout << day;
 
    return 0;
}