<백준> 7576번 토마토

문제

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

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

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

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

문제 해결 과정:

- bfs사용

- 입력을 받을때 1인 부분은 방문했음을 표시하고 큐에 넣는다. -1인 부분은 방문했음을 표시한다.

- bfs를 사용하여 큐에 첫번째 원소를 꺼내어 주변 칸에 방문하지 않은 상자를 체크한다. 토마토가 있다면 큐에 넣는다. 이때 범위 밖에 상자는 체크하지 않는다.

- 이 과정을 큐가 빌때까지 반복한다.

- 이후 모든 상자가 방문했다면 가장 마지막에 나간 큐의 일 수를 출력하고 모든 상자를 방문하지 않았다면 -1을 출력한다.

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
 
int box[1001][1001];
bool visited[1001][1001] = { false };
int dir[2] = {1,-1 };
 
//모든 상자를 방문하였는지 체크하는 함수
bool check(int N,int M) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visited[i][j]) {
                return false;
            }
        }
    }
    return true;
}
 
// 좌표와 날짜를 가진 구조체
struct node {
    int x = 0;
    int y = 0;
    int cnt = 0;
 
    node(int a, int b, int c) {
        x = a;
        y = b;
        cnt = c;
    }
};
 
int main() {
 
    int M, N;
    queue<node> q;
 
    scanf_s("%d %d", &M, &N);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int x;
            scanf_s("%d", &x);
            box[i][j] = x;
            if (x == 1) {        //1일때 큐에 넣고 방문체크
                q.push(node{ i,j,0 });
                visited[i][j] = true;
            }
            else if (x == -1) {        //-1일때 방문체크
                visited[i][j] = true;
            }
        }
    }
    node lastNode{0,0,0};    //큐에서 나오는 마지막 노드를 저장할 공간
 
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        lastNode = q.front();
        q.pop();
 
        //4방향에 대해서 체크
        for (int i = 0; i < 2; i++) {        //x방향에 대해서 +1,-1
                int newX, newY;
                newX = x + dir[i];
                newY = y;
                if (!(newX<0 || newY<0 || newX>=N || newY>=M)) {    //상자 범위를 넘으면 무시
                    if (!visited[newX][newY]) {
                        q.push(node{ newX, newY, cnt+1});        //날짜를 하나 더한다
                        visited[newX][newY] = true;                //방문 표시
                }
            }
        }
        for (int i = 0; i < 2; i++) {        //y방향에 대해서 +1,-1
            int newX, newY;
            newX = x;
            newY = y+dir[i];
            if (!(newX < 0 || newY < 0 || newX >= N || newY >= M)) {
                if (!visited[newX][newY]) {
                    q.push(node{ newX, newY, cnt + 1 });
                    visited[newX][newY] = true;
 
                }
            }
        }
    }
    
    if (!check(N,M)) {
        cout << "-1" << endl;        //방문하지 않은 상자 있으면 -1 출력
    }
    else {
        cout << lastNode.cnt << endl;    //마지막 노드의 날짜 
    }
    return 0;
}