백준 2638 - 치즈

백준 2638 문제 바로가기

풀이

문제의 조건은 아래와 같다.

NxM 격자상에서 1로 표시된 부분은 치즈이고, 0으로 표시된 부분은 공기이다. 임의의 치즈의 위치(r, c)에서 상하좌우 4방향 중에서 외부 공기인 부분이 2곳 이상 존재한다면, 해당 치즈는 녹아서 없어진다.

이때 문제 설명에 있는 <그림 2>처럼 치즈로 둘러 싸여있는 위치에 0으로 표시된 공간은 외부 공기가 아니다. (그림은 링크에 접속해서 참고하자)

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.

---

풀이 과정은 2개의 단계로 구분된다.

1. 외부 공기 판별

가장 자리에서 (0 ,0) 시작하여 상하좌우 4방향으로 이동하며 모눈종이 값이 0인 위치를 모두 탐색한다. 탐색하는 과정에서의 (r, c)는 외부 공기에 해당되는 칸이다.

이를 처리하기 위해 DFS를 활용하였고, 중복방문을 처리하였다. 이 함수의 호출이 종료되고 나면 air[r][c] 값이 true인 경우에는 외부 공기에 해당한다는 의미가 된다.

2. 치즈 녹이기

모눈종이 상태를 입력 받을 때, 치즈의 위치는 큐(chee)에 저장하였다. 따라서 초기에 저장된 큐의 사이즈(sz)만큼 꺼내어 치즈의 위치를 얻고, 그 치즈를 녹일 수 있다면 외부 공기 정보를 담는 큐(newAir)에 저장한다. 만약 녹일 수 없다면 다시 치즈 큐(chee)에 저장한다.

치즈 큐의 크기(sz)만큼 반복이 끝났다면, 치즈가 녹아서 외부 공기와 맞닿은 위치를 바꾸어 주기 위하여 newAir의 정보를 하나씩 꺼내어 외부 공기를 다시 판별하기 위해 dfs 함수를 호출한다.

두 가지 단계가 끝났을 때마다 1초가 소요된다.

소스 코드

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


int N; // 세로
int M; // 가로

const int dr[] = { -1,1,0,0 };
const int dc[] = { 0,0,-1,1 };

inline static bool isRange(int& r, int& c) {
    return 0 <= r && r < N && 0 <= c && c < M;
}


int m[100][100]; // 0: 빈 공간, 1: 치즈
int ans; // 치즈가 모두 녹아 없어지는데 걸리는 시간

struct pos {
    int r;
    int c;
    pos(int r, int c) {
        this->r = r;
        this->c = c;
    }
};
queue<pos> chee;

// 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다.
// 치즈 주위의 4변 중에서 2변 이상이 실내온도 공기와 접촉하면, 치즈는 녹아서 없어진다.
// 모눈 종이의 맨 가장자리에는 치즈가 놓이지 않는다.

// 외부 공기 판별
bool air[100][100];
void dfs(int r, int c) {
    air[r][c] = true;
    for (int d = 0; d != 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (isRange(nr, nc) && !air[nr][nc] && m[nr][nc] == 0) {
            dfs(nr, nc);
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N >> M;
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            cin >> m[r][c];
            if (m[r][c] == 1) {
                chee.push(pos(r, c));
            }
        }
    }
    
    // 초기 외부 공기 판별
    dfs(0, 0);

    while (!chee.empty()) {
        queue<pos> newAir;

        // air에서 true로 되어있는 부분은 외부 공기
        int sz = (int)chee.size();
        for (int s = 0; s != sz; ++s) {
            const pos now = chee.front();
            chee.pop();
            int airCnt = 0; // 외부 공기와 닿는 변의 개수
            for (int d = 0; d != 4; ++d) {
                int nr = now.r + dr[d];
                int nc = now.c + dc[d];
                if (air[nr][nc]) {
                    ++airCnt;
                }
            }
            if (airCnt >= 2) {
                newAir.push(now);
            }
            else {
                chee.push(now); // 녹지 않는 치즈는 큐에 다시 추가
            }
        }

        // 외부 공기로 바뀐 부분을 처리
        while (!newAir.empty()) {
            const pos& now = newAir.front();
            m[now.r][now.c] = 0;
            dfs(now.r, now.c);
            newAir.pop();
        }
        ++ans;
    }

    cout << ans;
    return 0;
}