백준 7576 - 토마토 (C++)

 

 

상자엔 익은 토마토와 익지 않은 토마토가 있다.

하루가 지나면 익은 토마토 주위 4방향에 있는 익지 않은 토마토는 익는다.

모든 토마토가 익을 때까지 시간이 얼마나 걸릴까?

 

문제 풀이

배열에 토마토의 정보를 담고 (전체 순회 -> 토마토 정보 업데이트 -> 모두 익었나 확인)의 과정을 반복하면 쉽게 해결할 수 있다. 본인이 해결한 방법은 약간 다르다. 익은 토마토의 위치를 모두 queue에 삽입한 뒤, 하나씩 뽑으며 BFS 방식으로 문제를 해결하였다.

 

풀이 코드

struct Data
{
    std::pair<int, int> Pos;
    int Days = 0;
};

먼저, queue에 삽입할 데이터 구조체를 만들어주었다.

익은 토마토의 위치와 며칠째에 익었는지를 저장하는 구조체이다.

int Width = 0;
int Height = 0;

std::cin >> Width >> Height;

std::vector<std::vector<int>> Map(Height, std::vector<int>(Width, 0));
std::queue<Data> Grown;

for (int i = 0; i < Height; i++)
{
    for (int j = 0; j < Width; j++)
    {
        std::cin >> Map[i][j];

        if (Map[i][j] == 1)
        {
            Grown.push({ { i, j }, 0 });
        }
    }
}

다음은 입력을 받아주었다.

입력을 받으면서 익은 토마토는 queue에 따로 삽입해주었다.

std::vector<int> DirX = { 1, 0, -1, 0 };
std::vector<int> DirY = { 0, 1, 0, -1 };

int Answer = 0;

while (Grown.size() > 0)
{
    Data CurData = Grown.front();
    Grown.pop();

    Answer = std::max(Answer, CurData.Days);

    for (int i = 0; i < 4; i++)
    {
        std::pair<int, int> NearTomato = { CurData.Pos.first + DirY[i], CurData.Pos.second + DirX[i]};

        if (NearTomato.first < 0 || NearTomato.second < 0 || NearTomato.first >= Height || NearTomato.second >= Width)
        {
            continue;
        }

        if (Map[NearTomato.first][NearTomato.second] == 0)
        {
            Map[NearTomato.first][NearTomato.second] = 1;
            Grown.push({ NearTomato, CurData.Days + 1});
        }
    }
}

다음은 BFS 구현코드이다.

 

먼저, 익은 토마토 하나를 꺼내서 주변 4방향에 익지 않은 토마토가 있나 검사한 뒤, 있다면 해당 토마토를 다시 queue에 삽입해주었다. 토마토가 익으려면 하루가 지나므로 Days에 +1을 해서 삽입해주었다.

 

Answer은 답을 저장할 변수인데 이 값은 계속 갱신해주었다.

for (int i = 0; i < Height; i++)
{
    for(int j = 0; j < Width; j++)
    {
        if (Map[i][j] == 0)
        {
            std::cout << -1;
            return 0;
        }
    }
}

std::cout << Answer;

return 0;

마지막에 아직 익지 않은 토마토가 있나 검사한 뒤, 있다면 -1을 출력하고 없다면 Answer 을 출력하도록 해주었다.

 

코드 전문

#include <iostream>
#include <set>
#include <queue>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

struct Data
{
    std::pair<int, int> Pos;
    int Days = 0;
};

int main()
{
    Init();

    int Width = 0;
    int Height = 0;

    std::cin >> Width >> Height;

    std::vector<std::vector<int>> Map(Height, std::vector<int>(Width, 0));
    std::queue<Data> Grown;

    for (int i = 0; i < Height; i++)
    {
        for (int j = 0; j < Width; j++)
        {
            std::cin >> Map[i][j];

            if (Map[i][j] == 1)
            {
                Grown.push({ { i, j }, 0 });
            }
        }
    }

    std::vector<int> DirX = { 1, 0, -1, 0 };
    std::vector<int> DirY = { 0, 1, 0, -1 };

    int Answer = 0;

    while (Grown.size() > 0)
    {
        Data CurData = Grown.front();
        Grown.pop();

        Answer = std::max(Answer, CurData.Days);

        for (int i = 0; i < 4; i++)
        {
            std::pair<int, int> NearTomato = { CurData.Pos.first + DirY[i], CurData.Pos.second + DirX[i]};

            if (NearTomato.first < 0 || NearTomato.second < 0 || NearTomato.first >= Height || NearTomato.second >= Width)
            {
                continue;
            }

            if (Map[NearTomato.first][NearTomato.second] == 0)
            {
                Map[NearTomato.first][NearTomato.second] = 1;
                Grown.push({ NearTomato, CurData.Days + 1});
            }
        }
    }

    for (int i = 0; i < Height; i++)
    {
        for(int j = 0; j < Width; j++)
        {
            if (Map[i][j] == 0)
            {
                std::cout << -1;
                return 0;
            }
        }
    }

    std::cout << Answer;

    return 0;
}