2025/02/16 백준 2638 치즈

난이도: G3

알고리즘: BFS

 

https://www.acmicpc.net/problem/2683

 

1. 문제 탐색

 

제한 시간: 1초, 메모리 제한: 128MB

 

격자가 나오고 연쇄적으로 일어나는 상황이므로 BFS를 이용한다.

 

2. 코드 설계하기

- BFS를 구현하기 위해 치즈 위치가 들어가는 큐를 선언한다.

- 치즈 내부 공간과 외부 공간을 구분하는 것이 중요하다.

그리고 치즈가 녹아서 없어졌을 때, 그 영향에 의해 내부 공간->외부 공간이 되는 위치들을 알아내는 것이 중요하다.

-> 따로 함수를 작성

- 녹아 없어질 치즈를 따로 자료구조에 보관한 뒤에 한 번에 외부 공간으로 바꿔야한다. 치즈 상태를 하나씩 바꾸고, 다음 녹을 치즈를 판단하게 되면, 앞서 치즈 상태를 바꾼 것에 영향을 받아 제대로 상태 변화가 이루어지지 않을 것이다. 

-> 따로 큐를 선언

 

3. 시도회차별 수정 사항

 

한번에 통과

 

4. 정답코드

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

using namespace std;

int dr[4] = {1,-1,0,0};
int dc[4] = {0,0,1,-1};
queue<pair<int,int>> cheese, temp; //치즈 위치

bool verify(int n, int m, int r, int c)
{
    if(r<0 || r>=n || c<0 || c>=m)
    {
        return false;
    }
    return true;
}

vector<vector<int>> makeNewOutside(int n, int m, vector<vector<int>> board) //외부 공간으로 전환
{
    while(!temp.empty())
    {
        int r = temp.front().first;
        int c = temp.front().second;
        
        board[r][c] = -1;

        for(int j=0; j<4; j++)
        {
            if(verify(n, m, r+dr[j], c+dc[j]) && board[r+dr[j]][c+dc[j]]==0)
            {
                board[r+dr[j]][c+dc[j]] = -1;
                temp.push({r+dr[j], c+dc[j]});
            }
        }

        temp.pop();
    }

    return board;
}

int main()
{
    int n, m;
    int ans = 0;

    cin>>n>>m;

    vector<vector<int>> board(n, vector<int>(m,0)); 

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>board[i][j];
            
            if(board[i][j]==1)
            {
                cheese.push({i,j});
            }
        }
    }

    //치즈 내부 공간, 외부 공간 구분
    //내부: 0 , 외부: -1
    board[0][0] = -1;
    board[n-1][m-1] = -1;
    board[n-1][0] = -1;
    board[0][m-1] = -1;
    temp.push({0,0});
    temp.push({n-1,m-1});
    temp.push({0,m-1});
    temp.push({n-1,0});

    board = makeNewOutside(n, m, board);

    while(!cheese.empty())
    {
        int cheeseCnt = cheese.size();
        for(int i=0; i<cheeseCnt; i++)
        {
            int cnt = 0; //해당 위치의 외부와 맞닿아 있는 면의 수
            for(int j=0; j<4; j++)
            {
                int nextR = cheese.front().first+dr[j];
                int nextC = cheese.front().second+dc[j];
                if(verify(n, m, nextR, nextC) && board[nextR][nextC] == -1)
                {
                    cnt += 1;
                }
            }

            if(cnt>=2) //이제 녹을 치즈
            {
                temp.push(cheese.front());
            }
            else
            {
                cheese.push(cheese.front());
            }
            cheese.pop();
        }

        board = makeNewOutside(n, m, board);

        ans += 1;
    }

    cout<<ans;
}