[백준 2638번] 치즈 (C++)

문제링크 : https://www.acmicpc.net/problem/2638

2638번: 치즈

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[101][101];
int visited[101][101];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
queue<pii>q;
int N, M, result;

void bfs(int y, int x) //외부 공기는 -1로
{
    queue<pii>qq;
    qq.push({y, x});
    visited[y][x]=1;

    while(!qq.empty())
    {
        auto [yy, xx] = qq.front();
        qq.pop();

        if(!arr[yy][xx]) arr[yy][xx]=-1;
        else continue;

        for(int i=0; i<4; i++)
        {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            if(ny > N || ny < 1 || nx > M || nx < 1 || visited[ny][nx]) continue;
            visited[ny][nx]=1;
            qq.push({ny, nx});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            cin >> arr[i][j];
        }
    }

    bfs(1, 1); // 가장자리는 무조건 공기

    while(1) // 치즈가 다 녹을때 까지
    {
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=M; j++)
            {
                if(arr[i][j]==1) //치즈일 때
                {
                    int cnt = 0;
                    for(int k=0; k<4; k++) //치즈 주변 공기 확인
                    {
                        int ny = i + dy[k];
                        int nx = j + dx[k];
                        if(arr[ny][nx]==-1) cnt++; 
                    }
                    if(cnt>=2) q.push({i, j}); //녹는 치즈 위치 저장
                }
            }
        }

        if(q.empty()) break; //녹일 치즈가 없으면 종료

        while(!q.empty())
        {
            auto [y, x] = q.front();
            q.pop();
            arr[y][x] = -1; //치즈 -> 공기
            for(int i=0; i<4; i++)
            {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if(!arr[ny][nx]) bfs(ny, nx); //내부 공기가 외부 공기와 만남 (0 -> -1)
            }
        }
        result++; //시간 증가
    }
    cout << result;

    return 0;
}

구현할 부분이 꽤 많은 문제다.

구현해야할 대상은 다음과 같다.

1. 치즈 외부 공기 / 내부 공기 파악
 * 외부 공기 = -1, 내부 공기 = 0, 치즈 1

2. 녹일 수 있는 치즈 위치 파악

3. 해당 치즈를 녹이고 녹은 치즈와 인접한 내부 공기를 외부 공기와 합침

4. 모든 치즈가 녹을 때까지 2 ~ 3 반복

먼저 외부 공기와 내부 공기를 구분해주기 위해 외부 공기에 대해서는 -1로 초기화를 진행해준다.

문제에서 맨 가장자리는 무조건 공기인 것을 확인할 수 있으므로 첫 가장자리인 1, 1을 기준으로 해당 칸과 붙어있는 공기들에 대해서 -1로 초기화를 진행한다.

 

다음으로 녹일 수 있는 치즈의 위치를 파악한다.

반복문을 돌리면서 현재 위치가 치즈 일때 상하좌우 탐색을 통해 인접한 칸에 외부공기가 있을 때마다 카운팅을 하여 카운팅이 2이상이면 해당 위치를 큐에 저장해준다.

상하좌우 탐색을 할때 범위에 대한 조건을 설정해줄 필요가 없는데, 이는 문제에서 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정했기 때문이다.

그래서 치즈의 상하좌우를 탐색해도 범위 밖으로 나갈 일이 아에 없다.

 

이후 큐에서 치즈가 녹아서 공기가 되므로 현재 값을 -1로 바꿔준다.현재 값이 공기가 됐으므로 인접한 상하좌우 칸에 내부 공기 (값 : 0) 가 있는지 확인하고 있다면 외부 공기 (값 : -1)로 바꿔준다.이때도 위와 마찬가지로 범위 조건을 설정해줄 필요가 없다.

현재 큐에 담긴 값에 대해서 이를 반복해주고, 반복문이 종료되면 시간을 증가시킨다.

 

위 2문단의 내용을 계속 반복하다가 치즈가 다 녹아서 큐에 넣을 값이 없어지면 종료시켜준다.