BOJ 2636번 : 치즈

BFS를 처음 배웠을때는 무작정 돌리면 끝나는 건줄 알았는데... 이걸 또 응용하는 문제들이 생겨버릴줄을 몰랐다.

 

문제의 핵심은 "외부 공기와 첩촉한 부분"만 시간이 지날수록 없어진다는 것이다.

 

위 <그림 1> 처럼 중간에 구멍이 있을 경우에는 외부공기와 차단되어있기에 구멍과 맞닿아 있는 부분은 녹아내리지 않는다.

 

그냥 [0][0] 위치부터 외부 공기를 계속 BFS를 통해 점령해가면서 접촉하는 치즈를 시간별로 녹이는 방법이 정석적일 수도 있으나, 치즈의 모양이 복잡할 경우 시간 초과가 날 수도 있을것 같아 새로운 방식으로 접근하였다.

 

먼저, [0][0]을 시작으로 BFS를 시작하여 외부 공기와 맞닿는 치즈의 테두리를 찾아낸다.

 

이후에는 찾아낸 테두리를 외부 공기라고 생각하고, BFS를 통해 또 맞닿아 있는 치즈를 찾아내는 방식이다.

 

이 방식을 적용할 경우, 매 반복문 마다 전체를 연산할 필요 없이 테두리 치즈만큼의 연산만을 하기에 효율적이다. 

 

또한, 구멍의 경우에도 처음엔 치즈 안에 갇혀있기 때문에 구멍을 감싸고 있는 치즈가 테두리가 되어 외부 공기로 판단될때 BFS에 빠지지 않고 들어가 예외가 없어진다.

 

<소스코드>

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
 
void Solve(int all, int r, int c, vector<vector<int>> map, vector<vector<bool>> chk, queue<pair<int,int>> air_q) {
    int y_arr[4] = { -1,1,0,0 }; // up, down, left, right
    int x_arr[4] = { 0,0,-1,1 };
 
    int res = all;
    int r_res = 0;
    int cnt = 0;
    vector<queue<pair<int, int>>> vq(2);
    queue<pair<int, int>> tem_q;
    int chk_map[100][100] = { 0, };
 
 
    while (all != 0) { // 치즈 다 녹을때까지
        r_res = res;
        while (!air_q.empty()) {// 돌려서 외부 바운더리를 찾음
            int y = air_q.front().first;
            int x = air_q.front().second;
            air_q.pop();
 
            for (int i = 0; i < 4; i++) {
                if (chk[y + y_arr[i]][x + x_arr[i]] == false) {
                    chk[y + y_arr[i]][x + x_arr[i]] = true;
                    if (map[y + y_arr[i]][x + x_arr[i]] == 0)
                        air_q.push(make_pair(y + y_arr[i], x + x_arr[i]));
                    else {
                        tem_q.push(make_pair(y + y_arr[i], x + x_arr[i])); // 경계 찾는 큐에 넣음
                        map[y + y_arr[i]][x + x_arr[i]] = 0;
                        all--;
                    }
                }
            }
        }
        res = res - tem_q.size();
        cnt++;
        air_q.swap(tem_q); // 스왑 해서 경계가 외부 공기가 되게 함. -> 구멍 있어도 겉의 경계가 외부 공기가 되므로 해결됨.
        tem_q = {};
    }
    cout <<cnt<<endl<<r_res << endl;
}
 
int main() {
 
    int r, c;
    int all = 0;
    cin >> r >> c;
    vector<vector<int>> map(r+2, vector<int>(c + 2, 0)); // 치즈 지도
    vector<vector<bool>> chk(r + 2, vector<bool>(c + 2, true)); // 방문 배열
    queue<pair<int, int>> air_q;
 
    for (int i = 1; i < r+1; i++) {
        for (int j = 1; j < c+1; j++) {
            cin >> map[i][j];
            chk[i][j] = false;
            if (map[i][j])
                all++;
        }
    }
    
    air_q.push(make_pair(1, 1)); // 시작점 넣어서 바운더리 찾기
    map[1][1] = 0; // 외부 공기
    chk[1][1] = true; // 시작점 방문
    Solve(all, r, c, map, chk, air_q);
 
}

 

<문제>

www.acmicpc.net/problem/2636

2636번: 치즈