[ 백준 7576 ] 토마토 (C++)

백준의 토마토(7576) 문제입니다.

( 문제보기 )

[ 문제설명 ]

- 입력으로 토마토 상자의 가로,세로의 길이와 토마토 상자의 상태가 주어집니다.

- -1 은 토마토가 없는 칸, 0은 익지 않은 토마토, 1은 익은 토마토입니다.

- 익은 토마토가 상하좌우 4방향 중 한 방향이라도 익지 않은 토마토가 있으면 토마토를 익게 만들 수 있습니다.

- 모든 토마토가 다 익을 수 있는 최소의 날짜, 혹은 모든 토마토가 다 익을 수 없는 경우 -1을 출력하면 됩니다.

[ 문제풀이 ]

1) 맵을 입력 받을 때, 토마토가 있는 위치를 Queue

2) 토마토가 있는 위치에서부터 BFS를 돌려주시고, 토마토를 익게 하는데 걸리는 시간을 계속 ++ 해주시면 됩니다.

3) BFS가 모두 끝나고 나서 맵 전체를 돌면서 익지 않은 토마토가 있다면 -1을 출력시켜면되고, 모든 토마토가

   다 익은 경우에는 걸리는 시간을 출력하시면 됩니다.

4) 위와 같이 시간에 대한 변수를 하나 더 만들어줘서 계산하는 방법도 있지만, BFS의 Leveling Skill 을 사용해도 쉽게 구할

   수 있습니다. 소스코드는 Leveling Skill 하는 방법까지 2개를 참고하겠습니다.

[ 소스코드 - BFS Leveling Skill 이용 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1 ,0, 0 };
 
queue<pair<int, int>> Q;
 
void Initialize()
{
    memset(MAP, 0, sizeof(MAP));
    memset(Visit, false, sizeof(Visit));
    Answer = 0;
}
 
void Input()
{
    cin >> M >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 1)
            {
                Q.push(make_pair(i, j));
                Visit[i][j] = true;
            }
        }
    }
}
 
bool Check_Tomato_State()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == 0) return false;
        }
    }
    return true;
}
 
void BFS()
{
    int Day = 0;
    while (Q.empty() == 0)
    {
        int Qs = Q.size();
        for (int q = 0; q < Qs; q++)
        {
            int x = Q.front().first;
            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 (Visit[nx][ny] == false && MAP[nx][ny] == 0)
                    {
                        MAP[nx][ny] = 1;
                        Visit[nx][ny] = true;
                        Q.push(make_pair(nx, ny));
                    }
                }
            }
        }
        Day++;
    }
 
    if (Check_Tomato_State() == false) cout << -1 << endl;
    else cout << Day - 1 << endl;
}
 
void Solution()
{
    BFS();
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ 소스코드 - 시간에 대한 변수 생성 후 계산 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1 ,0, 0 };
 
queue<pair<pair<int, int>, int>> Q;
 
void Initialize()
{
    memset(MAP, 0, sizeof(MAP));
    memset(Visit, false, sizeof(Visit));
    Answer = 0;
}
 
void Input()
{
    cin >> M >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 1)
            {
                Q.push(make_pair(make_pair(i, j), 0));
                Visit[i][j] = true;
            }
        }
    }
}
 
bool Check_Tomato_State()
{
    /*for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cout << MAP[i][j] << " ";
        }
        cout << endl;
    }*/
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == 0) return false;
        }
    }
    return true;
}
 
void BFS()
{
    int t;
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        t = 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 (Visit[nx][ny] == false && MAP[nx][ny] == 0)
                {
                    MAP[nx][ny] = 1;
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), t + 1));
                }
            }
        }
    }
 
    if (Check_Tomato_State() == false) cout << -1 << endl;
    else cout << t << endl;
}
 
void Solution()
{
    BFS();
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}