[Baekjoon(백준)][2636번] 치즈(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "치즈" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 사각형 모양의 판 위에 놓인 치즈가 공기 중에서 녹는 과정을 시뮬레이션하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

2636번: 치즈

문제 개요

"치즈" 문제는 사각형 모양의 판 위에 놓인 치즈가 공기 중에서 녹는 과정을 시뮬레이션하는 문제입니다. 치즈는 1×1 크기의 정사각형 칸으로 나뉘어져 있으며, 공기와 접촉한 칸은 한 시간 후에 녹습니다. 목표는 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아 있는 치즈 조각의 크기를 구하는 것입니다.

해결 방법

이 문제는 깊이 우선 탐색(DFS) 알고리즘을 사용하여 해결할 수 있습니다. 매 시간마다 외부 공기와 접촉하는 치즈의 위치를 찾아 녹이고, 치즈가 완전히 녹을 때까지 반복합니다.

코드 구현

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

int width, height;
int maps[102][102];
bool visited[102][102];
vector<pair<int, int>> q;

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

// 외부 공기와 접촉하는 치즈를 찾는 함수
void dfs(int y, int x) {
    visited[y][x] = true;
    if (maps[y][x] == 1) {
        q.push_back({y, x});
        return;
    }
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= height || nx >= width) continue;
        if (visited[ny][nx]) continue;
        dfs(ny, nx);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> height >> width;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            cin >> maps[i][j];
        }
    }
    int time = 0;
    int prev = 0;
    while (true) {
        fill(&visited[0][0], &visited[0][0] + 102 * 102, 0);
        q.clear();
        dfs(0, 0);
        prev = q.size();
        for (auto it : q) {
            maps[it.first][it.second] = 0;
        }
        bool isClear = true;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (maps[i][j] == 1) isClear = false;
            }
        }
        time++;
        if (isClear) break;
    }
    cout << time << "\n";
    cout << prev << "\n";
}

코드 설명

위 코드는 매 시간마다 외부 공기와 접촉하는 치즈를 찾아 녹입니다. DFS 알고리즘을 사용하여 외부 공기에 닿은 치즈의 위치를 확인하고, 해당 위치의 치즈를 녹입니다. 또한, 치즈가 모두 녹기 전과 후의 치즈 조각 크기를 계산하여 출력합니다.

결론

"치즈" 문제는 DFS 알고리즘을 사용하여 해결할 수 있으며, 매 시간마다 외부 공기와 접촉하는 치즈를 찾아 녹이고, 치즈가 모두 녹을 때까지 반복하는 방식으로 해결합니다.