백준 7576번: 토마토 (그래프 탐색과 순회)

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

 

 

 

 

 

 

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

 

---------------------------------------------------------------------------------------------------

1. 문제 해석

BFS를 통해, 1로 지정된 익은 토마토 위치에서부터 주위 토마토가 익을 때까지 걸리는 시간을 최단경로로써 저장할 수 있다.

다만, 시작점인 익은 토마토가 여러 곳일 수 있기 때문에, 각 BFS전에 visited를 초기화해서

적적하게 노드들을 모두 방문할 수 있도록 코드를 설계해야 한다.

 

 

2. 주의점

토마토들이 모두 익지 못하는 경우에는 -1을 출력해야 하는데,

모두 익지 못한다는 뜻은 추상적으로는 익은 토마토들로부터 BFS를 수행해도 접근하지 못하는 토마토(노드)가 존재한다는 뜻이고,

최단경로가 갱신이 되지 못한다는 의미가 되기도 한다.

 

처음에 구현할 때는 INF(임의의 매우 큰 수)로 초기화했던 distance 배열이 그대로 INF인 경우 (물론 접근하지 못하는 -1, 토마토가 없는 칸은 그냥 -1로 두었다. ) -1을 출력하고 종료하도록 하였다.

그러나 이 방식대로 하니 distance 배열을 모두 탐색하는 과정으로 인해 시간초과가 뜨는 것 같았다. 

 

나의 생각의 주안점은 다음과 같았다. 

2차원 배열을 그래프 탐색 할 때 모든 노드들을 방문하지 못했다는 사실을 distance 배열을 완전 탐색하지 않고 알 수 있는 방법은 뭐가 있을까? 

 

-> 조사 결과 그런 방법은 없는 것 같았다. 

 다시 생각해보아도, BFS는 인접 노드들을 방문하면서 색칠하거나 거리를 갱신할 뿐, 전체적으로 해당 노드를 방문했는지 여부를 알 수 있는 건 visited 라는 또 다른 배열을 완전 탐색하여 조사하는 법 밖에 없다.

 

그래서, BFS를 수행하는 방법에 문제가 있었다는 걸 알았다. 

 

초기에 BFS를 수행하는 것은 익은 토마토가 존재하기만 한다면 큐에 넣고 바로 BFS를 수행하는 방법이었다. 

이렇게 하면 한 익은 토마토에서 다른 토마토들이 익을 때까지 걸리는 시간을 전체적으로 구할 수 있다. 

그 다음 visit을 초기화 한 후, 

다시 익은 토마토를 찾아내어 그 토마토로부터 인접한 다른 모든 토마토들이 익을 때까지 걸리는 시간을, 더 최소한의 시간이 되게끔 조건을 걸어 최소 시간으로 갱신을 하려고 했다. 

 

그런데 이렇게 하지 않고도 쉽게 동시에 같은 거리를  갱신할 수 있는 방법이 있었다. 

바로 먼저 익은 토마토 노드들을 큐에 모두 넣어놓은 뒤에 BFS를 수행하는 것이다! 

(왜 이 방법을 생각하지 못했지?!)

이렇게 하면 각 시작점에서 같은 거리에 있는 노드들을 번갈아가면서 방문할 수 있다.

(여전히 이전 거리보다 최단일때만 갱신하도록 하는 것은 동일하다. )

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#define TRUE 1
#define FALSE 0
#define INF 1987654
using namespace  std;
int N,M,max_=-1, answer=-1;
int map[1001][1001];
int dis[1001][1001] = {0,};
int visited[1001][1001];
int dir[4][2] = {{-1,0}, {0,1}, {1,0} ,{0,-1}};
queue <pair<int, int> > Q;

int Cango(int r, int c) //인덱스 범위 초과하지 않는 지 확인
{
    if(r >=1 && r <= N && c >= 1 && c <= M)
        return 1;
    return 0;
}

void BFS() //BFS 수행
{
    while(!Q.empty())
    {
        int r = Q.front().first;
        int c = Q.front().second;
        Q.pop();
        if(visited[r][c] == TRUE)
            continue;
        visited[r][c] = TRUE;
        for(int i=0;i<4;i++)
        {
            int next_r = r + dir[i][0];
            int next_c = c + dir[i][1];
            if(Cango(next_r, next_c) && map[next_r][next_c] == 0)
            {
                if(dis[next_r][next_c] > dis[r][c] + 1) {
                    dis[next_r][next_c] = dis[r][c] + 1;
                     Q.push(make_pair(next_r,next_c));
                }
               
            }
        }
    }
}

void restart()
{
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            visited[i][j] = FALSE;
        }
    }
}

void find() //익은 토마토를 찾아서 큐에 넣은뒤 ,BFS를 호출
{
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(map[i][j] == 1) {
                //printf("%d %d BFS\n", i,j);
                dis[i][j] = 0;
                Q.push(make_pair(i,j));
            }
        }
    }
        BFS();
}

void init() //거리는 무한대로 초기화, 맵과 visited는 0으로 초기화. 
{
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            map[i][j] = 0;
            visited[i][j] = 0;
            dis[i][j]= INF;
        }
    }
}
int main()
{
    scanf("%d %d", &M, &N); //상자의 가로 ,세로 길이 입력
    init();
    for(int i=1;i<=N;i++) //입력을 받되 익지 않는 토마토를 찾기 위해 토마토가 없는 곳은 distance도 -1로 갱신: 아래 코드를 보면 이해된다.
    {
        for(int j=1;j<=M;j++)
        {
            scanf("%d", &map[i][j]);
            if(map[i][j] == -1)
                dis[i][j] = -1;
        }
    }
    find(); //익은 토마토를 찾아 BFS를 수행하는 함수 수행. 
    
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(dis[i][j] > answer)
                answer = dis[i][j];
        }
    }
    
    if(answer >= INF) // 거리가 무한 대인 곳이 있다 == 안 익은 토마토가 있다. (방문 못한 노드). 토마토가 없는 곳을 -1로 초기화 해둔 이유. 
    {
        printf("-1\n");
        return 0;
    }
    printf("%d\n",answer);
}