[백준 2638] 치즈 (C++) - 50

문제

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

2638번: 치즈

생각

문제를 잘못읽어 한참 헤맸다.

문제에서 "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다." 를 못읽어 어려움을 겪었다.

 

다시 읽으니 풀이 방법이 보였다.

1. 먼저 가장 외각은 무조건 외부공기가 되므로 (0, 0)을 시작으로 BFS 탐색을 실시해 외부 공기를 선별한다.

   - 이때 외부 공기를 찾는 기준은 map[0][0]의 값이 -1 일때 그 주변의 값이 1 이거나 -1이면 외부공기로 설정했다.

 

2. 그후 map[y][x]의 값이 1 일때 그 상하좌우에 값이 1이거나 0이면 배열 chz[y][x]의 값을 0에서부터 1개씩 늘렸다.

    - 외부 공기는 전부 -1로 설정을 했으므로 내부공기는 초기 그대로 0이 된다.

 

3. map을 다시 순회해 녹는 치즈들을 외부공기로 설정한다.

    - 이때 녹는 치즈들은 chz[y][x]의 값이 2이하인 경우이다.

    - 내부공기 또는 다른 치즈와 닿는 면이 2개 이하인 경우

 

코드

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
#define pii pair<int, int>

int n, m, day;
int map[101][101];
int chz[101][101];
bool vst[101][101];
int d[4][2] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} };
queue<pii> q;

void bfs() {
    memset(vst, false, sizeof(vst));
    memset(chz, 0, sizeof(chz));
    //외부공기인지 판단
    q.push({0, 0});
    vst[0][0] = true;
    map[0][0] = -1;
    while(!q.empty()) {
        auto[cy, cx] = q.front();
        q.pop();
        for(int i = 0; i < 4; i++) {
            int ny, nx;
            ny = cy + d[i][0];
            nx = cx + d[i][1];
            if(ny < 0 || nx < 0 || ny > n - 1 || nx > m - 1) continue;
            if(map[ny][nx] == -1 || map[ny][nx] == 0) {
                if(!vst[ny][nx]){
                    map[ny][nx] = -1;
                    vst[ny][nx] = true;
                    q.push({ny, nx});
                }
            }
        }
    }
    //녹는 치즈인지 판단
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(map[i][j] == 1) {
                for(int k = 0; k < 4; k++) {
                    int ny, nx;
                    ny = i + d[k][0];
                    nx = j + d[k][1];
                    if(map[ny][nx] == 1 || map[ny][nx] == 0) chz[i][j]++;
                }
            }
        }
    }
    //녹는 치즈들 -1로
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(chz[i][j] <= 2 && map[i][j] == 1) {
                //cout << "melt " << i << " " << j << " " << "chz[i][j] = " << chz[i][j] << "\n";
                map[i][j] = -1;
            }
        }
    }
    return;
}

int main() {
    //입력
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            int a; cin >> a;
            map[i][j] = a;
        }
    }
    //치즈 모두 녹았는지 확인
    while(1) {
        bool cheese = false;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(map[i][j] == 1) cheese = true;
            }
        }
        if(cheese == true) {
            day++;
            bfs();
            cout << "\n";
        }
        else {
            cout << day;
            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 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0


8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0
0 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0
*/