[백준] 골드4 2636번 - 치즈 (C++)

접근법

1. 덩어리의 테두리를 검출하는 방법을 생각하자. (컴퓨터 비전 수업에서 비슷한 기법을 배웠다.)

2. 다 녹기 하루 전의 치즈 량을 요구한다. 매일 치즈량을 기록해야한다.

3. 치즈가 언제 다 녹을지 모르니 무한 루프로 접근한다.

 

 

 

 

 

 

 

 

풀이

1. 먼저 N x M의  2차원 벡터를 준비하여 입력 받는다.

2. 무한 루프를 선언하고  BFS 함수를 돌린다.

3. 함수 내의 BFS 는 0,0에서 시작하며 0에 대한 좌표는 큐에, 1에 대한 좌표는 따로 선언해둔 벡터 배열에 저장한다.

4. BFS의 while문이 끝나고 1의 좌표들을 저장한 벡터 배열을 순회하며 해당 좌표를 0으로 바꾼다.

5. 테두리의 크기를 입력받는 배열을 준비하여 1의 좌표를 담은 벡터 배열의 크기를 담는다.

6. 만약 벡터 배열의 크기가 0이라면 치즈가 모두 녹았다는 것이므로 무한 루프를 종료하고 일 수 와 1의 개수를 출력한다.

7. 벡터 배열의 크기가 0이 아니라면 다시 2번으로 가서 반복한다.

 

 

 

 

 

#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cmath>
#include <string>
#include <queue>


using namespace std;
int N,M, L, R;

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

vector<int> oneCnt; // 치즈 테두리의 수 -> 이것으로 하루 전 치즈의 양을 구한다.
bool loopEnd = false;
int answer = 0; // 일 수를 담는다.

void BFS(vector<vector<int>> &map){
    vector<vector<int>> vst(N, vector<int>(M, 0));
    vector<pair<int, int>> oneList;
    queue<pair<int, int>> q1;
    q1.push({0,0});
    vst[0][0] = 1;

    while(!q1.empty()){
        int a = q1.front().first;
        int b = q1.front().second;

        q1.pop();

        for(int i = 0; i < 4; i++){
            int na = a + dir[i][0];
            int nb = b + dir[i][1];

            if(na > -1 && na < N && nb > -1 && nb < M){
                if(vst[na][nb] == 0){
                    if(map[na][nb] == 0){
                        // 0 이면 큐에 담는다.
                        q1.push({na, nb});
                    }
                    else{
                        //cout << "na : " << na << " nb : " << nb << '\n';
                        // 1 이면 큐가 아니라 벡터에 담는다.
                        oneList.push_back({na, nb});
                    }
                    vst[na][nb] = 1;
                }
            }
        }
    }
    // 벡터에 담아둔 1의 좌표들을 모두 0으로 만든다.
    for(int i = 0; i < oneList.size(); i++){
        map[oneList[i].first][oneList[i].second] = 0;
    }
    oneCnt.push_back(oneList.size());
    
    // 치즈가 다 녹았으면 종료
    if(oneList.empty()){
        loopEnd = true;
    // 아니면 하루 더 해야하니까 일 수를 증가시킨다.
    }else{
        answer ++;
    }

}

int main(){
    cin >> N >> M;
    vector<vector<int>> map(N, vector<int>(M, 0));

    for(int i = 0; i < N * M; i++){
        cin >> map[i / M][i % M];
    }

    while(!loopEnd){
        BFS(map);
    }
    // oneCnt의 뒤에서 두번째 칸에 다 녹기 하루 전의 1의 개수가 담겨있다.
    cout << answer << '\n' << oneCnt[oneCnt.size() - 2] << '\n';
    
    return 0;
}