[BaekJoon/백준] 2638번 치즈

 

어제부로, 모든 골드 4문제를 끝냈고

덕분에 골드2로 승격했다.

 

 

오늘 문제는, 조금 더 쉽게 풀 수 있었는데 그렇지 못한 문제였다.

 

 

나는 모눈종이의 맨 가장자리(가생이)들을 모두 dfs를 돌아주며 치즈의 바깥쪽과 안쪽을 구분해주려했는데,

문제에 이런 내용이 있었다

 

즉, dfs(0,0) 한번만 해서 체크해주면 치즈 바깥쪽과 안쪽을 구분하기에 충분하다는 것이다.

 

이것만 빼면 다른 분들의 풀이와 비슷하다.

 

 

1. 먼저 치즈의 바깥쪽을 구분해주기 위해, dfs를 돌면서 해당 부분을 -1로 체크해준다.

 

2. 전체를 for문을 돌며, 현재 칸이 치즈(=1)인 경우 상하좌우 중에 -1인 곳이 두 개 이상 있으면 치즈를 없애버린다(=0)

 

반복

/*
 
 가생이 한바퀴를 각각 dfs처리해주면
 외부와 내부를 분리하는데 충분할듯.
 
 (0,0) ~ (0,M)
 (0,M) ~ (N,M)
 
 (0,0) ~ (N,0)
 (N,0) ~ (N,M)
 */



#include <iostream>
#include <cstring>
using namespace std;

int N, M;

int MAP[100][100];
bool VISIT[100][100];


int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};

bool flag = false;
int DAYS;

void outside(int x, int y) {
    
    VISIT[x][y] = true;
    MAP[x][y] = -1; // 바깥영역은 -1로 처리
    
    
    for(int i = 0; i < 4; i++) {
        
        int tx = x + mx[i];
        int ty = y + my[i];
        
        if(tx < 0 || tx >= N || ty < 0 || ty >= M)
            continue;
        
        if(!VISIT[tx][ty] && MAP[tx][ty] <= 0)
            outside(tx, ty);
    }
    
    
}
int main() {
    
    
    cin >> N >> M;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
    
    
    while(1) {
        
        flag = false;

        memset(VISIT, 0, sizeof(VISIT));
        for(int i = 0; i < M; i++) {
            if(!VISIT[0][i] && MAP[0][i] <= 0)
                outside(0, i);
        }
        
        for(int i = 0; i < N; i++) {
            if(!VISIT[i][M] && MAP[i][M] <= 0)
                outside(i, M);
        }
        
        for(int i = 0; i < N; i++) {
            if(!VISIT[i][0] && MAP[i][0] <= 0)
                outside(i, 0);
        }
        
        for(int i = 0; i < M; i++) {
            if(!VISIT[N][i] && MAP[N][i] <= 0)
                outside(N, i);
        }
        
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                
                if(MAP[i][j] == 1) { // 치즈라면
                    
                    flag = true; // 치즈가 남아 있다.
                    
                    int CNT = 0;
                    
                    for(int k = 0; k < 4; k++) {
                        
                        int tx = i + mx[k];
                        int ty = j + my[k];
                        
                        if(tx < 0|| tx >= N || ty < 0 || ty >= M)
                            continue;
                        
                        if(MAP[tx][ty] == -1)
                            CNT++;
                        
                    }
                    
                    if(CNT >= 2) {
                        MAP[i][j] = 0; // 치즈 바로 지워버림.
                    }
                }
                
            }
        }
        
        if(flag == false)
            break;
        
        DAYS++;
        
    }
    
    
    cout << DAYS << "\n";
    
}

 

즉 위 코드에서 나는 for문을 네번을 처리하면서 outside를 호출하는데,

그냥 outside(0, 0) 한번만 호출해도 이 문제를 풀 수 있다.

 

 

소요 시간 : 40분