백준 7576번 토마토

문제 링크입니다: https://www.acmicpc.net/problem/7576

전형적인 BFS 문제였지만 모든 토마토가 익지 않은 경우도 고려해야했기 때문에 살짝 까다로운 문제였습니다.

알고리즘은 아래와 같습니다.

1. 창고를 입력 받는데 1이면 덱에 넣고, -1이면 noTomato를 증가시킵니다.

2. 창고에 있는 토마토가 모두 익었다면 0을 출력하고 아니라면 BFS 함수를 호출합니다.

3. BFS 함수를 호출하였는데 덱이 비어있다면 모든 토마토가 익을 수 없는 경우이므로 -1을 반환합니다.

4. 현재 덱 사이즈만큼 for문을 돌리면서 front에 있는 좌표를 꺼내 창고 범위 내에 있는 상하좌우에 있는 안 익은 토마토를 익힌 뒤 해당 좌표를 덱에 넣고 front를 pop 시킵니다.

5. 현재 덱 사이즈만큼 for문을 돌린 뒤에는 하루가 지나므로 day를 증가시킵니다.

6. 덱이 비었고 allRipe 함수가 true를 반환하면 day를 반환하고, 덱이 비었는데 allRipe 함수가 false를 반환하면 모든 토마토가 익을 수 없으므로 -1을 반환합니다.

#include <iostream>

#include <deque>

using namespace std;

 

const int MAX = 1000;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int N, M;

int tomato[MAX][MAX];

deque<pair<int, int>> dq;

int noTomato;

 

//토마토가 전부 익었는지 확인

bool allRipe(void)

{

        int possible = M * N - noTomato;

        int tomatoCnt = 0;

 

        for (int i = 0; i < M; i++)

                 for (int j = 0; j < N; j++)

                         if (tomato[i][j] == 1)

                                 tomatoCnt++;

 

        return possible == tomatoCnt;

}

 

int BFS(void)

{

        int day = 0;

 

        //처음부터 익힐 수 있는 토마토가 없는 경우

        if (dq.empty())

                 return -1;

 

        while (!dq.empty())

        {

                 int currentSize = dq.size();

 

                 for (int i = 0; i < currentSize; i++)

                 {

                         int y = dq.front().first;

                         int x = dq.front().second;

 

                         for (int i = 0; i < 4; i++)

                         {

                                 int nextY = y + moveDir[i].y;

                                 int nextX = x + moveDir[i].x;

 

                                 //다음 토마토가 범위 안에 있고 안 익었을 경우에만

                                 if (0 <= nextY && nextY < M && 0 <= nextX && nextX < N && tomato[nextY][nextX] == 0)

                                 {

                                          tomato[nextY][nextX] = 1;

                                          dq.push_back(make_pair(nextY, nextX));

                                 }

                         }

 

                         dq.pop_front();

 

                         //익힐 수 있는 토마토를 전부 익혔고 전부 익었을 경우

                         if (dq.size() == 0 && allRipe())

                                 return day;

                         //익힐 수 있는 토마토는 전부 익혔지만 안 익은 토마토 존재

                         else if (dq.size() == 0 && !allRipe())

                                 return -1;

                 }

                 day++;

        }

}

 

int main(void)

{

        cin >> N >> M;

 

        for (int i = 0; i < M; i++)

                 for (int j = 0; j < N; j++)

                 {

                         cin >> tomato[i][j];

 

                         if (tomato[i][j] == 1)

                                 dq.push_back(make_pair(i, j)); //익은 토마토는 덱에 넣는다

                         else if (tomato[i][j] == -1)

                                 noTomato++; //토마토를 넣을 수 없는 칸

                 }

 

        if (dq.size() == M * N - noTomato)

        {

                 cout << 0 << endl; //모든 토마토 다 익었을 경우

        }

        else

        {

                 int result = BFS();

                 cout << result << endl;

        }

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~