BOJ 2638: 치즈 [C++]

문제

2638번: 치즈

 

이번학기 자료구조 과제에서 본 문제와 유사했다.

이 문제는 BFS는 여러번 돌려야 했다.

 

외부 공기에만 녹고, 내부 공기에는 녹지 않는다.
치즈는 모눈종이 맨 가장자리에는 있을 수 없다.

 

(0, 0) 부터 시작하여 0인 부분을 모두 2로 채워주었다. (외부 공기를 표기하기 위함)

void makeAirBox(int x, int y) {
    std::queue<std::pair<int, int>> trace;
    std::queue<std::pair<int, int>> record;
    trace.push({x, y});
    record.push({x, y});
    visited[x][y] = true;

    while (!trace.empty()) {
        int cur_x = trace.front().first;
        int cur_y = trace.front().second;
        trace.pop();

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

            if (nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1) {
                continue;
            }
            if (visited[nx][ny]) {
                continue;
            }
            if (matrix[nx][ny] == 0) {
                trace.push({nx, ny});
                record.push({nx, ny});
                visited[nx][ny] = true;
            }
        }
    }
    while (!record.empty()) {
        int cur_x = record.front().first;
        int cur_y = record.front().second;
        record.pop();
        matrix[cur_x][cur_y] = 2;
    }
}

 

한번 BFS를 돌리고 나면, 내부 공기, 치즈를 제외한 나머지 부분은 모두 2로 채워진다.

그 상태에서 해당칸이 치즈이면서 외부 공기와 2칸 이상 맞닿는 칸은 외부 공기인 2로 바꾸어준다.

void melt() {
    std::queue<std::pair<int, int>> toMelt;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1) {
                int cnt = 0;
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x < 0 || x > n - 1 || y < 0 || y > m - 1) {
                        continue;
                    }
                    if (matrix[x][y] == 2) {
                        cnt++;
                    }
                }
                if (cnt >= 2) {
                    toMelt.push({i, j});
                }
            }
        }
    }
    while (!toMelt.empty()) {
        int x = toMelt.front().first;
        int y = toMelt.front().second;
        toMelt.pop();
        matrix[x][y] = 2;
    }
}

 

치즈가 녹으면서 내부공기였던 것들이 외부공기로 바뀌는 경우가 있으므로,

외부 공기이지만 아직 BFS로 방문하지 않은 곳에서

BFS를 돌려 내부공기였던 것들까지 외부 공기로 바꾸어준다.

처음 (0, 0)에서 BFS를 돌린 것을 제외한 위 과정을 한 사이클(문제에서의 1시간)으로 생각하고,

모눈 종이가 모두 외부공기로 채워질 때까지 진행한다.

    makeAirBox(0, 0);
    while (!allMelted()) {
        melt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 2 && visited[i][j] == false) {
                    makeAirBox(i, j);
                }
            }
        }
        ans++;
    }

 

 

 

 

---

전체 코드

#include <iostream>
#include <queue>

int n;
int m;
int matrix[101][101] = {{0, }, };
bool visited[101][101] = {{false, }, };

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

int ans = 0;

bool allMelted() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1) {
                return false;
            }
        }
    }
    return true;
}

void makeAirBox(int x, int y) {
    std::queue<std::pair<int, int>> trace;
    std::queue<std::pair<int, int>> record;
    trace.push({x, y});
    record.push({x, y});
    visited[x][y] = true;

    while (!trace.empty()) {
        int cur_x = trace.front().first;
        int cur_y = trace.front().second;
        trace.pop();

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

            if (nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1) {
                continue;
            }
            if (visited[nx][ny]) {
                continue;
            }
            if (matrix[nx][ny] == 0) {
                trace.push({nx, ny});
                record.push({nx, ny});
                visited[nx][ny] = true;
            }
        }
    }
    while (!record.empty()) {
        int cur_x = record.front().first;
        int cur_y = record.front().second;
        record.pop();
        matrix[cur_x][cur_y] = 2;
    }
}

void melt() {
    std::queue<std::pair<int, int>> toMelt;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1) {
                int cnt = 0;
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x < 0 || x > n - 1 || y < 0 || y > m - 1) {
                        continue;
                    }
                    if (matrix[x][y] == 2) {
                        cnt++;
                    }
                }
                if (cnt >= 2) {
                    toMelt.push({i, j});
                }
            }
        }
    }
    while (!toMelt.empty()) {
        int x = toMelt.front().first;
        int y = toMelt.front().second;
        toMelt.pop();
        matrix[x][y] = 2;
    }
}

int main() {
    std::cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> matrix[i][j];
            visited[i][j] = false;
        }
    }

    makeAirBox(0, 0);
    while (!allMelted()) {
        melt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 2 && visited[i][j] == false) {
                    makeAirBox(i, j);
                }
            }
        }
        ans++;
    }

    std::cout << ans << "\n";

    return 0;
}