백준 2636 치즈 c++ [컴공과고씨]

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

2636번: 치즈

이 문제는 탐색 문제지만 고려해야할 것이 있다. 첫번째는 무조건 적인 탐색이 아니라 외부쪽에 있는 치즈를 전부다 방문하면 카운트 그 다음 안쪽에 있는 치즈 전부 탐색 후 카운트 이런식으로 순차적으로 가면서 카운팅을 해주어야 된다. 

그래서 나는 bfs안에 기본적인 구조가 큐를 한번 쓰는 거라면 큐를 2번을 사용하여 구현을 해주었다. 

일단 (0,0)에서 시작을 해서 탐색을 시작하여 1을 만났을 때는 temp큐에 넣어주고 0일 경우 q에 넣어 탐색을 계속해서 진행해준다. 이렇게 반복하면 가장자리의 치즈는 temp 큐에 모이게 된다. 그리고 카운트를 올려주고 temp큐에 있는 것을 q에 다시 넣어준다. 이렇게 되면 1에 있는 치즈에서 탐색을 진행하고 다음 가장자리 치즈는 temp 큐에 모이고 이것을 반복해 주는 것이다. 이렇게 하다보면 temp 큐가 비어있게 되고 temp큐가 비면 q가 비게되어서 반복문이 끝나게 된다.

그리고 q반복문을 시작할 때 q의 사이즈를 저장해두면 치즈가 다 없어지기 직전의 치즈의 개수를 알 수 있다.

 

전체코드

#include <iostream>
#include <queue>
using namespace std;
int r, c;
int map[101][101];
bool visit[101][101];
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
int cnt, area;
void bfs(){
    queue<pair<int, int>> q;
    queue<pair<int, int>> temp;
    q.push(make_pair(0, 0));
    while(!q.empty()){
        area = q.size(); // 남은 치즈 개수 체크
        while(!q.empty()){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int i = 0; i < 4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (nx >= 0 && nx < c && ny >=0 && ny <r){
                    if(!visit[ny][nx] && map[ny][nx] == 1){
                        temp.push(make_pair(nx, ny)); // 가장자리 치즈 만 저장
                    }else if(!visit[ny][nx] && map[ny][nx] == 0){
                        q.push(make_pair(nx, ny)); //탐색 진행
                    }
                    visit[ny][nx] = true;
                }
            }
        }
        while(!temp.empty()){
            q.push(temp.front());
            temp.pop();
        }
        cnt++;
    }   
}
int main(){
    cin >> r >> c;
    for (int i = 0; i < r;i++){
        for (int j = 0; j < c;j++){
            cin >> map[i][j];
        }
    }
    visit[0][0] = true;
    bfs();
    cout << cnt-1 << '\n'; // while문 구조상 카운트가 한번 더 됨.
    cout << area << '\n';
    return 0;
}

사용 문법 : bfs