[C++] 백준 2636 - 치즈

www.acmicpc.net/problem/2636

2636번: 치즈

<풀이>

1. 치즈 맵을 입력받는다.

2. 바깥쪽 공기와 맞닿는 치즈를 없앤다.

3. 치즈가 모두 없어졌을 때까지 걸린 시간과, 그 전 치즈 개수를 출력한다.

 

<해법>

1. 바깥쪽 공기와 맞닿는 치즈를 없애는 방법

=> 탐색(BFS, DFS) 이용합니다. 탐색을 이용해서 바깥쪽 공기가 어디까지 퍼져있는지 확인합니다. 탐색 진행 도중에 치즈를 발견했을 경우, 바깥 공기와 맞닿는 치즈이므로 치즈를 없애는 식으로 진행하였습니다.

 

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
//4방향 : 북,동,남,서
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int height, width;
int map[100][100];
bool visited[100][100];
 
int resTime = 0;
int resCheeze = 0;
 
//구조 : 좌표
struct pos {
    int x, y;
};
 
//맵에 치즈가 없는지 확인 : 없으면 true, 있으면 false
bool noCheeze() {
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (map[i][j] == 1) {
                return false;
            }
        }
    }
    return true;
}
 
//치즈 없애기
void removeCheeze() {
    
    //방문 배열 초기화
    memset(visited, false, sizeof(visited));
 
    //바깥쪽 공기만 탐색
    queue<pos> q;
    q.push({ 0,0 });
    visited[0][0] = true;
 
    while (!q.empty()) {
        pos cur = q.front();
        q.pop();
 
        //4방향 탐색
        for (int i = 0; i < 4; i++) {
            pos nxt = cur;
            nxt.x += di[i];
            nxt.y += dj[i];
 
            //범위 밖 or 방문했던 경우 -> continue
            if (nxt.x < 0 || nxt.y < 0 || nxt.x >= height || nxt.y >= width || visited[nxt.x][nxt.y]) {
                continue;
            }
 
            //공기일 경우 -> 큐에 넣기(계속 탐색을 해야하므로)
            if (map[nxt.x][nxt.y] == 0) {
                q.push(nxt);
            }
            //치즈일 경우 -> 바깥 공기와 맞닿는 치즈이므로 공기로 바꾸어줌, 큐에 담지 않음(더 이상 탐색X)
            else {
                map[nxt.x][nxt.y] = 0;
            }
            visited[nxt.x][nxt.y] = true;
        }
    }
 
}
 
//치즈 개수 세기
int countCheeze() {
    int output = 0;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (map[i][j] == 1) {
                output++;
            }
        }
    }
    return output;
}
 
int main() {
 
    //입력
    cin >> height >> width;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            cin >> map[i][j];
        }
    }
 
    while (true) {
 
        //치즈가 없을 경우 -> 종료
        if (noCheeze()) {
            break;
        }
 
        //치즈 개수 갱신
        resCheeze = countCheeze();
 
        //치즈 없애기
        removeCheeze();
 
        //시간 + 1
        resTime++;
    }
 
    //출력
    cout << resTime << "\n" << resCheeze;
}

 

탐색과 구현에 대해 알아볼 수 있는 문제였습니다.