백준 2638 치즈 (C++)

안유태·2022년 9월 20일
0

알고리즘

목록 보기
41/239

2638: 치즈

시뮬레이션과 그래프 탐색을 적절히 섞은 문제이다. 치즈가 모두 녹는 시간을 구해야하며 치즈는 내부 공기가 아닌 외부 공기와 두 변 이상 접해있어야 녹는다. 우선 처음에 치즈에 해당하는 좌표를 v벡터에 저장해주고 반복문을 돌려준다. inside()합수에서 (0, 0)을 시작으로 외부 공기를 2로 바꿔주어 내부 공기와 분리해주었고 치즈가 2와 접해있는 변이 두개 이상이면 0으로 바꿔주고 q에 넣어주었다. 이 과정을 반복하며 res 변수로 그 횟수를 저장해 출력해주었다.
오타 하나 때문에 30분을 날려먹었다. 오타를 주의하자.



#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, M, res = 0;
int A[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
vector<pair<int, int>> v;
queue<pair<int, int>> q;

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

        A[y][x] = 2;

        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;
            if (A[ny][nx] != 0) continue;

            A[ny][nx] = 2;

            q.push({ ny,nx });
        }
    }
}

void solution() {
    q.push({ 0,0 });

    while (!v.empty()) {
        inside();

        for (int i = 0; i < v.size(); i++) {
            int y = v[i].first;
            int x = v[i].second;
            int count = 0;

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

                if (A[ny][nx] == 2) count++;
                if (count == 2) break;
            }

            if (count == 2) {
                A[y][x] = 0;
                v.erase(v.begin() + i);
                i--;
                q.push({ y,x });
            }

        }

        res++;
    }

    cout << res;
}

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

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> A[i][j];

            if (A[i][j] == 1) {
                v.push_back({ i,j });
            }
        }
    }

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글