[2636] 치즈

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

2636번: 치즈

<문제>

치즈의 사이에 있는 빈공간은 치즈에 아무런 영향을 미치지 못한다.

이 부분을 예외처리하려고 생각하면 꽤 헤멜 수 있지만,

판의 가장자리는 항상 빈 공간이라는 점 + 치즈에 영향을 주는 공기는 항상 판의 가장자리와 연결된점에서 착안해

bfs()의 시작점이 항상 {0, 0}으로 고정되었다고 생각할 수 있다.

이후로는 인접한 공기를 탐색하며, 동시에 인접한 치즈를 녹여주는 bfs-시뮬레이션을 진행해준다.

 

turn과 함께, 마지막으로 남아있는 치즈의 개수또한 저장해두어야 하는데

이는 치즈의 개수를 입력받을때에 미리 파악해둔 후,

시뮬레이션 도중 계속해서 업데이트 해주며 2개의 변수를 사용하여 저장해두면 되겠다.

<소스코드>

#include <stdio.h>
#include <string.h>
 
#include <queue>
using namespace std;
int n, m, cnt, a[101][101];
int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
queue<int> q;
bool visit[101][101];
void bfs(void) {
    int y, x, ty, tx, i;
    memset(visit, false, sizeof(visit));
    q.push(0);
    q.push(0);
    visit[0][0] = true;
    while (!q.empty()) {
        ty = q.front();
        q.pop();
        tx = q.front();
        q.pop();
        for (i = 0; i < 4; i++) {
            y = ty + dy[i];
            x = tx + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (a[y][x] == 1) {
                a[y][x] = 0;
                visit[y][x] = true;
                cnt--;
            }
            if (visit[y][x] == false && a[y][x] == 0) {
                q.push(y);
                q.push(x);
                visit[y][x] = true;
            }
        }
    }
}
int main(void) {
    int i, j, pre = 0;
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 1) cnt++;
        }
    }
    i = 0;
    while (cnt > 0) {
        pre = cnt;
        bfs();
        i++;
    }
    printf("%d\n%d", i, pre);
    return 0;
}