[백준 7576] 토마토

토마토

문제설명

첫 줄에 가로 M , 세로 N 그리고 각각의 가로 세로에 맞춰 0,1,-1의 입력이 각각 주어진다.
이때 0은 익지 않은 토마토, 1은 익은 토마토, -1은 토마토가 없는 상태를 의미한다.
토마토 1개가 익어있으면 상하좌우 방향의 토마토는 다음날 익는다. 그리고 대각선은 익지 않는다.
모든 토마토가 익는데 걸리는 날짜를 구한다. 만약 토마토가 전부 익을 수 없다면 -1을 출력 시킨다.
이미 익어있는 상태면 0을 출력한다.

알고리즘

1. 입력 받는 즉시 1이 들어오면 queue 에 담아 놓는다 -> 이는 익어있는 토마토가 모두 다른 토마토에 영향을 끼치게 하기 위함이다.
2. bfs함수를 실행한다.
3. visited 배열을 조회 하는데, 최대 값이 모든 토마토가 익는데 걸린 기간이라고 간주 할 수 있다.
   고로 가장 큰 값을 찾되, 전부 다 익지 못하는 경우를 찾는다.
4. 모든 토마토가 익지 못한 경우는 graph[][]==0 을 갖고있지만 visited[][]==0이 있는 경우이다.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <queue>
#include <utility>
using namespace std;
#define MAX 1000

int graph[MAX][MAX];
int visited[MAX][MAX];
int answer = 0;
int N, M;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
queue <pair<int, int>> q;
void bfs()
{
    while (!q.empty())
    {
        int x = q.front().first;//queue의 앞의 값 불러오기 
        int y = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];//위치이동 반경 계산
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)//범위내에 해당하는 부분이면 
            {
                if (graph[nx][ny] == 0 && visited[nx][ny] == 0)//주변에 벽이 없고 방문하지 않아서 방문 해도 되는 경우 
                {
                    visited[nx][ny] = visited[x][y]+1;
                    q.push(make_pair(nx,ny));
                }
            }

        }
    }

}

int main(void)
{
    cin >> M >> N;
    for (int i = 0; i < N; i++)//연결 관계 입력 받기
    {
        int x;
        for (int j = 0; j < M; j++)
        {
            cin >> x;
            graph[i][j] = x;
            if (x == 1)//모든 시작점 토마토를 고려하기 위해 바로 queue에 넣기
                q.push({ i,j });
        }
    }

    bfs();//함수 실행

    int max = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (visited[i][j] > max)//가장 큰 값 찾기
                max = visited[i][j];
            if (visited[i][j] == 0 && graph[i][j] ==0)//토마토가 익지 않는 것이 있는 경우 -> 방문해야 하지만 방문하지 못한 경우
            {
                cout << -1 << endl;
                return 0;
            }
        }
    }

    cout <<max<< endl;//최댓 값 -1을 출력하면 걸린 일 수 -> 다 익어있는 경우도 포함 
    return 0;
}

테스트 케이스

1.토마토가 전부 익는 것이 불가능한 경우

graph[0][0]=0이지만, 주변이 -1이여서 익을 수 없는 경우가 발생한다.

bfs함수 후 visited[i][j] == 0 && graph[i][j] ==0 조건이 발생하면 바로 -1을 출력하면 된다.
방문해야했지만 방문하지 못했다는 의미로 간주 할 수 있음

2.시작할 때 익어있는 토마토가 여러개인 경우 -> 제일 고민 많이 했던 경우

처음 시작할 때 값을 입력 받고 나중에 graph[][]=1인 값을 찾아서 함수를 실행하면 동시에 토마토가 익는 것을 고려하지 못한다. 따라서 테스트케이스 입력 동시에 queue에 넣어버리고 실행시키면 된다.

이렇게 하지 않으면 처음 1인 값 먼저해서 총 익는데 시간이 달라진다.

3.토마토가 이미 다 익어있는 경우

이러한 경우 bfs함수 순회후 visited를 보면 어차피 최대 값이 0이기 때문에 따로 고려하지 않아도 처리 가능하다.

고찰
결과적으로 다른 bfs문제와 동일했지만 좀 더 고려할 사항이 있는 문제였다. 입력 받는 동시에 queue에 넣어서 동시에 처리해야하는 데서 헤맸지만 bfs를 좀 더 잘 이해할 수 있게 된 것 같다.