[백준/c++] 2638 치즈

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

2638번: 치즈

 

✨ 문제풀이

 

n*m 격자 모양 행렬을 BFS로 해결하는 문제입니다. 그러나 반복해서 전체 격자를 검색하면서 치즈가 전부 녹아서 없어질 때까지 진행해야 합니다. 이 문제의 가장 핵심은 '외부 공기'와 '내부 공기'를 구분하는 일입니다. '외부 공기'와 접촉이 없고 치즈에 둘러싸인 내부 공기에 닿은 치즈 면은 녹지 않는 면입니다. 바로 이 공기를 구분할 때 BFS를 사용합니다. '내부 공기'를 구분해내는 것보다 외부공기를 표시해주는 게 훨씬 간단하기 때문에 외부공기는 계속해서 내부 공기와 다른 표시를 해줍니다.

 

모든 치즈가 녹을 때까지 얼마의 시간이 걸리는지 체크해야 하므로 반복적으로 모든 좌표를 검색합니다. n, m의 최대값이 100이므로 n*m 으로 1초 안에 연산 가능합니다.

 

🗓 코드

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

#define MAXINT 101

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

int map[MAXINT][MAXINT];
bool visited[MAXINT][MAXINT];

void initialize()
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            map[i][j] = 0;
}

void initialize_visited()
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            visited[i][j] = false;
}

void getInput()
{
    cin >> n >> m;
    initialize();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> map[i][j];
}

void check_outside_air()
{
    // 방문 기록을 모두 초기화
    initialize_visited();
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;

    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
            // 아직 체크하지 않은 외부 공기(0), 이미 체크한 외부 공기(-1)이 공존하므로
            // 치즈(1)가 아닌 좌표에 대해서 탐색
            if (map[ny][nx] != 1 && !visited[ny][nx])
            {
                visited[ny][nx] = true;
                map[ny][nx] = -1;
                q.push({ny, nx});
            }
        }
    }
}

void solve()
{
    int time = 0;
    while (1)
    {
    	// 1. 외부 공기 구분해서 체크
        check_outside_air();
        // 2. 모든 좌표를 탐색해서 이번에 녹을 치즈 위치 체크
        bool is_melting_cheese_exist = false;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (map[i][j] == 1)
                {
                    int count = 0;
                    for (int k = 0; k < 4; k++)
                    {
                        int ny = i + dy[k];
                        int nx = j + dx[k];
                        if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                            continue;
                        // map[i][j]와 맞닿는 외부공기(-1) 개수 체크
                        if (map[ny][nx] == -1)
                        {
                            is_melting_cheese_exist = true;
                            count++;
                        }
                    }
                    // map[i][j]와 외부 공기가 2면 이상 맞닿으므로 녹을 치즈(2)로 체크
                    if (count >= 2)
                        map[i][j] = 2;
                }
            }
        }
        // 위에서 체크한 녹을 치즈(2)를 외부 공기(-1)로 바꾸기
        if (is_melting_cheese_exist)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (map[i][j] == 2)
                        map[i][j] = -1;
                }
            }
        }
        // 3. 시간 1 증가
        time++;

        // 4. 아직 치즈가 남아있다면 반복
        bool is_cheese_left = false;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (map[i][j] == 1)
                    is_cheese_left = true;
            }
        }
        if (!is_cheese_left)
            break;
    }
    printf("%d\n", time);
}

int main(int argc, char const *argv[])
{
    // -1 : 외부 공기
    // 0 : 내부 공기
    // 1 : 치즈
    // 2 : 녹을 치즈
    initialize();
    getInput();
    solve();
    return 0;
}

 

2. DFS

void check_outside_air(int y, int x)
{
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= n || nx >= m)
            continue;
        if (map[ny][nx] != 1 && !visited[ny][nx])
        {
            visited[ny][nx] = true;
            map[ny][nx] = -1;
            check_outside_air(ny, nx);
        }
    }
}