백준 2638 - 치즈 - DFS

문제

문제링크 : https://www.acmicpc.net/problem/2638

풀이전략

1. 치즈의 내부공간과 외부공간이 구별되어있다. 이 문제에서 모눈종이에 맨 가장자리들에는 치즈가 놓이지 않는 것을 가정했기 때문에 이 4개의 부분을 기준으로 치즈의 바깥공간과 안 공간을 구별할 수 있다.
2. 치즈가 적어도 2변이상이 실내공기와 접촉하면 한시간이내로 녹으니, 각 치즈들이 공기와 어떻게 접촉되어있는지 찾아야한다.
3. 이문제는 치즈를 순차적으로 제거할 경우 갑자기 없었던 외부 공간이 발생하므로 문제를 틀리게 된다. 치즈를 제거에 관한 정보를 배열에 저장하고 일괄적으로 제거해야한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N, M;
int a[102][102];
// 치즈를 줄이는 것에 대한 정보를 저장한 배열
int adjustA[101][101];
// 치즈의 내부와 외부를 구별해주는 배열
int ch[102][102] = {false,};
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

// ch배열에 치즈 내부에는 1, 외부에는 -1을 넣어준다.
// value는 처음 시작하는 값이 외부인지 내부인지 알려준다. 
void findInterior(int r, int c, int value){
    for(int i=0; i<4; i++){
        int rr = r+dy[i];
        int cc = c+dx[i];
        if(ch[rr][cc] == 0 && a[rr][cc] == 0){
            ch[rr][cc] = value;
            findInterior(rr,cc, value);
        }
    }
}

int afterHour(){
    memset(adjustA, 0, sizeof(adjustA));
    // 한시간 뒤에 치즈를 어떻게 빼줘야 할지에 대한 정보를 저장하는 과정
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(a[i][j] == 1){
                int cnt = 0;
                for(int k=0; k<4; k++){

                    int ii = i+dy[k];
                    int jj = j+dx[k];

                    if(a[ii][jj] == 0 && ch[ii][jj]==-1) cnt++;
                }
                if(cnt>=2) adjustA[i][j] = 1;
            }
        }
    }
    int res = 0;
    // 치즈를 뺴주는 과정
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            a[i][j] = a[i][j] - adjustA[i][j];
            res += a[i][j];
        }
    }
    // 남아있는 치즈의 개수가 0인지 아닌지 return해줌
    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    memset(a, -1, sizeof(a));
    cin >> N >> M;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            cin >>a[i][j];
        }
    }
    int result = 1;
    while(1){
        
        memset(ch, 0, sizeof(ch));
        
        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
            	// 치즈가 아닌 외부 또는 내부 부분일때
                if(a[i][j] == 0){
                    // 치즈가 놓이지 않는 가장자리 부분에서부터 치즈 외부공기에 대한 영역을 시작한다. 
                    if((i==1 && j == 1) || (i==N && j==1) || (i==1 && j==M) || (i==N && j==M)){
                        findInterior(i,j, -1);
                    }
                    // 그 외는 모두 내부부분이다. 
                    else{
                        findInterior(i,j, 1);
                    } 
                }
                
            }
        }
        // 남아있는 치즈의 개수가 0이면 끝
        if(afterHour() == 0) break;
        result++;
    }
    cout<<result<<endl;

    return 0;
}

소감

영역의 내부, 외부를 구분해야한다는 점이 이문제에서 인상적이였다. 체크배열을 Int형으로 만들어 내부는 1, 외부는 -1을 넣어 서로 구별해주고, 내부인지 외부인지 모르는 부분은 0으로해준 것이 중요한 부분이다. 또한 이문제도 마찬가지로 순차적으로 치즈를 제거해주면 갑자기 외부가 발생하므로 제거해 줘야할 정보를 따로 저장하고 일괄적으로 치즈를 제거해야한다.