[Algorithm/C++17] 백준 2638 치즈

문제

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

2638번: 치즈

풀이 방법

입력이 주어졌을 때 치즈가 몇 시간만에 녹을지 계산하는 문제이다. 치즈는 4변 중에서 적어도 2변 이상이 외부 공기와 닿으면 정확히 1시간만에 녹는다. 치즈로 둘러싸인 내부 공기는 녹는데에 아무런 영향을 미치지 않는다.

 

그렇다면 내부 공기와 외부 공기를 어떻게 판별할까?

문제에서 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는다고 했으니, 가장자리에서 공기 칸 탐색을 시작하면 된다. 이렇게 하면 치즈에 막힌 공기는 탐색되지 않는다. 또한 녹을 치즈도 탐색하면서 계산해준다.

 

아래 코드에서는 따로 함수를 작성해 분리했다.

meltCheese: 2변 이상이 실내온도의 공기와 접촉한 치즈를 녹인다.

simulateAir: 외부 공기를 탐색하면서 맞닿은 치즈의 접촉 칸 수를 계산한다.

isThereCheese: 주어진 공간에 치즈가 있으면 true, 없으면 false를 반환한다.

코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};

void meltCheese(vector<vector<int>>& v, vector<vector<int>>& adjAir)
{
    int N = v.size();
    int M = v[0].size();
    // 치즈를 녹여 없앤다.
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(adjAir[i][j] >= 2)
            {
                v[i][j] = 0;
            }
            adjAir[i][j] = 0;
        }
    }
}

void simulateAir(vector<vector<int>>& v, vector<vector<int>>& adjAir)
{
    int N = v.size();
    int M = v[0].size();
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    queue<pair<int,int>> q;
    q.push({0,0});
    visited[0][0] = true;
    while(!q.empty())
    {
        auto cur = q.front();
        q.pop();
        int y = cur.first;
        int x = cur.second;
        for(int i=0; i<4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || ny >= N || nx < 0 || nx >= M)
                continue;
            if(visited[ny][nx]) 
                continue;
            // 치즈
            if(v[ny][nx])
            {
                adjAir[ny][nx]++;
            }
            // 공기
            else
            {
                visited[ny][nx] = true;
                q.push({ny,nx});
            }
        }
    }
}

bool isThereCheese(vector<vector<int>>& v)
{
    int N = v.size();
    int M = v[0].size();
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(v[i][j]) 
                return true;
        }
    }
    return false;
}

int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    vector<vector<int>> v(N, vector<int>(M));
    vector<vector<int>> adjAir(N, vector<int>(M, 0));
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            int t;
            scanf("%d", &t);
            v[i][j] = t;
        }
    }
    
    int answer = 0;
    while(isThereCheese(v))
    {
        simulateAir(v, adjAir);
        meltCheese(v, adjAir);
        answer++;
    }
    
    printf("%d", answer);
    return 0;
}

고찰

처음 문제를 보고 어렵다 생각했다. 하지만 가만히 생각해보니 그냥 밖에서 탐색을 시작하면 내, 외부 공기 판별이 쉽게 가능했다.