2638번 치즈

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

처음에 어떻게 접근할까 하다가 아래 그림처럼 생각하였다.

위의 노란색 칸에서 해당 지점(r, c)로 오는 횟수를 계산하여 2 이상인 곳을 0으로 바꿔주면 어떨까라고 생각했었다.

하지만 바로 많은 반례를 떠올렸다.(심지어 문제에 제시된 그림)

그래서 곧바로 다시 생각했다.

(0, 0)에서 dfs돌리고, 

1일 때는 해당 칸의 임시 배열(temp[행][열])을 1 증가시키고,

0이라면 그대로 계속 dfs를 돌린다.

그리고 temp[행][열]가 2 이상일 때는 m[행][열]을 0으로 바꿔준다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 101
 
int R, C, m[Max][Max], temp[Max][Max];
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool visit[Max][Max];
 
void dfs(int r, int c)
{
    visit[r][c] = true;
 
    for (int i = 0; i < 4; i++) {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= R || x < 0 || x >= C || visit[y][x]) {
            continue;
        }
 
        if (m[y][x]) {
            ++temp[y][x];
        }
        else {
            dfs(y, x);
        }
    }
}
 
int simulation()
{
    int ret = 0;
 
    while (true)
    {
        memset(temp, 0, sizeof(temp));
        memset(visit, false, sizeof(visit));
 
        bool stop = true;
 
        for (int i = 0; i < R && stop; i++) {
            for (int j = 0; j < C; j++) {
                if (m[i][j]) {
                    stop = false;
                    break;
                }
            }
        }
 
        if (stop) break;
 
        dfs(0, 0);
 
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (temp[i][j] >= 2) {
                    m[i][j] = 0;
                }
            }
        }
 
        ++ret;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%1d", &m[i][j]);
        }
    }
 
    printf("%d\n", simulation());
 
    return 0;
}