백준 2638 - 치즈 (C++)

 

 

매초 외부와 2칸 이상 접촉된 치즈가 녹아내린다.

모든 치즈가 녹아내리는데, 몇 초가 걸리는지 출력하면 된다.

 

문제 풀이

 

문제의 핵심은 치즈 내부와 외부를 어떻게 구분하느냐이다.

위의 그림처럼 치즈가 배치되어 있다면, 빨간 영역이 외부이고 파란 영역이 내부일 것이다.

외부를 구하는 법은 간단하다.

(0,0)을 시작으로 BFS를 돌리면 된다.

 

문제 조건을 보면, 가장자리에는 치즈를 배치하지 않는다는 조건이 있다.

즉, (0,0)은 항상 외부에 속하는 영역이고 이 점을 기준으로 BFS를 돌리면 외부를 파악할 수 있다.

 

BFS를 통해, 외부를 판별한 뒤 외부와 2칸 이삭 접촉한 치즈를 제거하면 된다.

 

이 과정이 1번 실행될 때마다, 1초가 지난다고 가정하며 치즈가 사라질 때까지 반복하면 된다.

 

풀이 코드

int Height = 0;
int Width = 0;
std::cin >> Height >> Width;

std::vector<std::vector<int>> Board(Height, std::vector<int>(Width, 0));
std::vector<std::vector<bool>> isVisit(Height, std::vector<bool>(Width, false));

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

먼저 입력을 모두 받아준다.

int TimeCount = 0;

while (BFSFunc(Board, isVisit) < Height * Width)
{
    TimeCount++;
}

이후, BFS를 돌려주며 시간을 1초씩 늘려주었다.

BFSFunc는 외부를 확인한 뒤, 치즈를 제거하는 과정까지 포함된 함수이다.

반환값은 외부의 칸 개수이다. 외부의 칸 개수가 전체 맵의 크기(높이 * 너비)와 같다면 치즈가 모두 녹았다고 판단하는 것이다.

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

int BFSFunc(std::vector<std::vector<int>>& _Board, std::vector<std::vector<bool>>& _isVisit)
{
    for (int i = 0; i < _isVisit.size(); i++)
    {
        std::fill(_isVisit[i].begin(), _isVisit[i].end(), false);
    }

    std::queue<std::pair<int, int>> BFS;
    BFS.push({ 0, 0 });
    _isVisit[0][0] = true;

    std::set<std::pair<int, int>> CheesePos;

    int EmptyCount = 1;

    while (BFS.size() > 0)
    {
        std::pair<int, int> CurPos = BFS.front();
        BFS.pop();

        for (int i = 0; i < 4; i++)
        {
            int NextX = CurPos.second + DirX[i];
            int NextY = CurPos.first + DirY[i];

            if (NextX < 0 || NextY < 0 || NextX >= _Board[0].size() || NextY >= _Board.size())
            {
                continue;
            }

            if (_Board[NextY][NextX] == 0 && _isVisit[NextY][NextX] == false)
            {
                _isVisit[NextY][NextX] = true;
                BFS.push({ NextY, NextX });

                EmptyCount++;
            }

            if (_Board[NextY][NextX] == 1)
            {
                CheesePos.insert({ NextY, NextX });
            }
        }
    }

    std::set<std::pair<int, int>>::iterator CurIter = CheesePos.begin();
    std::set<std::pair<int, int>>::iterator EndIter = CheesePos.end();

    while (CurIter != EndIter)
    {
        std::pair<int, int> CurPos = *CurIter;

        int Count = 0;

        for (int k = 0; k < 4; k++)
        {
            int NextX = CurPos.second + DirX[k];
            int NextY = CurPos.first + DirY[k];

            if (_isVisit[NextY][NextX] == true)
            {
                Count++;
            }

            if (Count >= 2)
            {
                _Board[CurPos.first][CurPos.second] = 0;
                break;
            }
        }

        CurIter++;
    }

    return EmptyCount;
}

 

isVisit 벡터의 경우, 계속 새로 만들어주는것보다 값만 바꿔주는 것이 더 빠를 것이라고 판단하여 함수의 처음 부분에 std::fill을 이용해 모든 값을 false로 초기화해주었다.

 

이후 평범하게 BFS를 돌려주었다.

isVisit가 true인 부분은 외부라고 판단할 수 있을 것이다.

 

이후, 치즈가 있는 칸을 전부 돌아주며 상하좌우 4방향중 2칸 이상이 외부인 치즈를 제거해주었다.

std::cout << TimeCount;

return 0;

  마지막으로 반환해주면 끝이다.

 

 

코드 전문

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

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


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

int BFSFunc(std::vector<std::vector<int>>& _Board, std::vector<std::vector<bool>>& _isVisit)
{
    for (int i = 0; i < _isVisit.size(); i++)
    {
        std::fill(_isVisit[i].begin(), _isVisit[i].end(), false);
    }

    std::queue<std::pair<int, int>> BFS;
    BFS.push({ 0, 0 });
    _isVisit[0][0] = true;

    std::set<std::pair<int, int>> CheesePos;

    int EmptyCount = 1;

    while (BFS.size() > 0)
    {
        std::pair<int, int> CurPos = BFS.front();
        BFS.pop();

        for (int i = 0; i < 4; i++)
        {
            int NextX = CurPos.second + DirX[i];
            int NextY = CurPos.first + DirY[i];

            if (NextX < 0 || NextY < 0 || NextX >= _Board[0].size() || NextY >= _Board.size())
            {
                continue;
            }

            if (_Board[NextY][NextX] == 0 && _isVisit[NextY][NextX] == false)
            {
                _isVisit[NextY][NextX] = true;
                BFS.push({ NextY, NextX });

                EmptyCount++;
            }

            if (_Board[NextY][NextX] == 1)
            {
                CheesePos.insert({ NextY, NextX });
            }
        }
    }

    std::set<std::pair<int, int>>::iterator CurIter = CheesePos.begin();
    std::set<std::pair<int, int>>::iterator EndIter = CheesePos.end();

    while (CurIter != EndIter)
    {
        std::pair<int, int> CurPos = *CurIter;

        int Count = 0;

        for (int k = 0; k < 4; k++)
        {
            int NextX = CurPos.second + DirX[k];
            int NextY = CurPos.first + DirY[k];

            if (_isVisit[NextY][NextX] == true)
            {
                Count++;
            }

            if (Count >= 2)
            {
                _Board[CurPos.first][CurPos.second] = 0;
                break;
            }
        }

        CurIter++;
    }

    return EmptyCount;
}

int main()
{
    Init();

    int Height = 0;
    int Width = 0;
    std::cin >> Height >> Width;

    std::vector<std::vector<int>> Board(Height, std::vector<int>(Width, 0));
    std::vector<std::vector<bool>> isVisit(Height, std::vector<bool>(Width, false));

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

    int TimeCount = 0;

    while (BFSFunc(Board, isVisit) < Height * Width)
    {
        TimeCount++;
    }

    std::cout << TimeCount;

    return 0;
}