백준 2638번 치즈 [C++]

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

 

 

#문제 해결 방법

 

친절하게도 가장자리에는 치즈가 놓이지 않는다고 했으니

외곽부터 외부공기를 탐색하고 난 후 남은 공기는

내부 공기로 취급하면 된다.

 

나는 외부 공기를 그냥 bool 배열을 사용해서 따로 표시했다.

기존의 맵이랑 같이 표시하는 방법이 더 효율이 좋을 듯 한데 

그냥 더 직관적인 방법을 사용했다.

 

1.외부공기를 확인한 후에

2. 외부공기 2개가 맞닿은 치즈 확인 -> 지우기

        findOx(0, 0);
        cheeseCheck();

를 반복하고 

치즈가 0이 될때 까지 반복된 순서를 출력 하면 된다.

 

#전체 코드

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

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int cheeseCount;
int n, m;
vector<vector<int>> world;
vector<vector<bool>> check;

bool boundary(int x, int y) {
    if (0 <= x && x < n && 0 <= y && y < m) return true;

    return false;
}

void findOx(int x, int y) {

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (boundary(nx, ny)) {
            if (world[nx][ny] == 0 && check[nx][ny] == false) {
                check[nx][ny] = true;
                findOx(nx, ny);
            }
        }

    }

}
void cheeseCheck() {
    for (int a = 0; a < n; a++) {
        for (int b = 0; b < m; b++) {
            if (world[a][b] == 1) {
                int oxCount = 0;
                for (int i = 0; i < 4; i++) {
                    int nx = a + dx[i];
                    int ny = b + dy[i];
                    if (boundary(nx, ny)) {
                        if (check[nx][ny] == true) {
                            oxCount++;
                        }
                    }

                }
                if (oxCount >= 2) {
                    world[a][b] = 0;
                    cheeseCount--;
                }
            }
        }
    }
}






int main() {
    //1. 일단 공기를 돌면서 치즈에 갖혀있는지 아닌지 판별한다
    // ->가장자리 공기를 탐색하고 외부 탐색이 안 되었다면 내부 공기
    //2.치즈를 녹이고 시간을 보낸후 치즈가 0개라면 시간 출력



    cin >> n >> m;
    world.resize(n, vector<int>(m, 0));


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> world[i][j];
            if (world[i][j] == 1) cheeseCount++;
        }
    }

    int phase = 0;
    while (cheeseCount > 0) {
        check.assign(n, vector<bool>(m, false));
        //외부 공기 확인
        check[0][0] = true;
        findOx(0, 0);
        //접촉 치즈 확인
        cheeseCheck();

        phase++;
    }

    cout << phase << '\n';

    return 0;
}