백준 2638번 [치즈](C++)-yes6686- 티스토리

백준 문제 풀이: 2638 [치즈]

---

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

문제 설명:

n×m 크기의 판에 치즈가 놓여 있습니다. 공기와 접촉한 치즈는 한 시간이 지나면 녹습니다. 치즈는 2변 이상이 공기와 접촉하면 녹게 됩니다. 모든 치즈가 녹을 때까지 걸리는 시간을 출력합니다.

입력:

• 첫째 줄에 판의 크기 n (1 ≤ n ≤ 100)과 m (1 ≤ m ≤ 100)이 주어집니다.
• 다음 n개의 줄에 치즈 상태를 나타내는 0과 1이 주어집니다. 1은 치즈가 있는 칸, 0은 공기가 있는 칸을 나타냅니다.

출력:

• 모든 치즈가 녹을 때까지 걸리는 시간을 출력합니다.

---

문제 해결 코드

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

int n, m;
int board[101][101];
int visited[101][101];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// BFS를 통해 외부 공기 탐색 및 치즈 녹이기
void bfs() {
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = 1;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

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

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visited[nx][ny]) continue;

            if (board[nx][ny] == 0) { // 공기라면
                visited[nx][ny] = 1;
                q.push({nx, ny});
            } else { // 치즈라면
                board[nx][ny]++; // 공기와 접촉한 횟수 증가
            }
        }
    }
}

// 치즈를 녹이고 상태를 갱신
bool meltCheese() {
    bool cheeseLeft = false;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] >= 3) { // 2변 이상 공기와 접촉한 치즈는 녹음
                board[i][j] = 0;
            } else if (board[i][j] == 1 || board[i][j] == 2) { // 치즈가 남아있는 경우
                board[i][j] = 1;
                cheeseLeft = true;
            }
        }
    }

    return cheeseLeft;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }

    int time = 0;
    while (true) {
        memset(visited, 0, sizeof(visited));
        bfs(); // 외부 공기 탐색 및 치즈 녹이기 준비
        if (!meltCheese()) break; // 치즈가 모두 녹았는지 확인
        time++;
    }

    cout << time << '\n';

    return 0;
}

예제

입력:
8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0

출력:
4

입력:
5 5
0 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 1 1
0 0 0 1 1

출력:
2

---

코드 설명

• 외부 공기 탐색: BFS를 통해 외부 공기를 탐색하며, 공기와 접촉한 치즈의 접촉 횟수를 증가시킵니다.
• 치즈 녹이기: 접촉 횟수가 2 이상인 치즈를 녹이며, 남아있는 치즈 여부를 확인합니다.
• 반복 종료: 더 이상 치즈가 남아있지 않으면 반복을 종료합니다.

시간 복잡도

• BFS의 시간 복잡도: O(n × m)
• 치즈 녹이기 반복: 최대 O(n × m)
• 전체 시간 복잡도: O((n × m)²)

---

결과

코드는 입력된 행렬에서 치즈가 모두 녹을 때까지 걸리는 시간을 정확히 계산합니다. BFS를 활용한 접근 방식으로 효율적으로 문제를 해결합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!