[알고리즘] 백준 2636

백준 2636번 치즈

해결 과정 요약

dfs(0,0)을 모든 치즈가 없어질 때까지 호출하고 before배열에 모든 치즈가 없어지기 직전 상태를 저장해주면 되는 문제다.
직전상태를 저장하고 치즈가 사라지는 것을 dfs함수에 구현해준다.

void dfs(int y, int x){
    visited[y][x] = 1;
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
        if(!visited[ny][nx]){
            if(a[ny][nx]){
                a[ny][nx] = 0;
                before[ny][nx] = 1;
                visited[ny][nx] = 1;
                continue;
            }
            else dfs(ny, nx);
        }
    }
}

위 함수를 보면 치즈의 가장자리를 찾으면 가장자리를 없애주고 before에 직전상태(가장자리)를 저장한다.
또한 가장자리 안쪽은 탐색이 안되게 하기 위해 visited를 1로 바꾸어준다.

 while(true){
        if(check()) break;
        else {
            fill(&visited[0][0], &visited[0][0] + 104*104, 0);
            fill(&before[0][0], &before[0][0] + 104*104, 0);
        }
        cnt++;
        dfs(0, 0);
    }

visited, before을 초기화 시키고 치즈가 다 없어졌는지 확인하면서 dfs함수를 반복적으로 돌아준다.
dfs를 하기 전에는 cnt값을 증가시켜준다.
이렇게 치즈가 다 없어지는데에 걸린 시간을 구할 수 있다.
cnt를 출력하고 before배열 안에 있는 1의 개수를 세어 출력해주면 끝.

풀이

#include <bits/stdc++.h>
using namespace std;

int N,M,cnt;
int a[104][104];
int before[104][104];
int visited[104][104];
int dy[4] = {-1, 0 ,1, 0};
int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x){
    visited[y][x] = 1;
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
        if(!visited[ny][nx]){
            if(a[ny][nx]){
                a[ny][nx] = 0;
                before[ny][nx] = 1;
                visited[ny][nx] = 1;
                continue;
            }
            else dfs(ny, nx);
        }
    }
}

bool check(){
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(a[i][j]) return false;
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> a[i][j];
        }
    }
    int cnt = 0;
    while(true){
        if(check()) break;
        else {
            fill(&visited[0][0], &visited[0][0] + 104*104, 0);
            fill(&before[0][0], &before[0][0] + 104*104, 0);
        }
        cnt++;
        dfs(0, 0);
    }
    cout << cnt << "\n";
    cnt = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(before[i][j]) cnt++;
        }
    }
    cout << cnt << "\n";
    return 0;
}

코멘트

나는 직전상태를 계속 저장하는 방식으로 구현했는데
그 이유는 치즈가 없어지기 직전에 dfs를 멈추는 방식이 떠오르지 않았기 때문이다.
이 글을 쓰고 조금 더 생각해봐야겠다.