[C++] 백준 2638 - 치즈 (직관적인 접근)

• 문제

• 풀이 과정

• 정의

• check 함수

• bfs 함수

• 최종 코드

• 잡담

백준 2638 : 치즈
난이도 : 골드 3

시간 : 1시간 20분 소요

 

 

 

문제

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

2638번: 치즈

풀이 과정

이 문제는 bfs를 사용하는 것이 유리하다.

이 문제를 봤을 때, 가장 중요하다고 생각했던 것은 내부와 외부를 구별하는 것이었다.

내부와 외부가 구별되지 않는다면 접하는 4개의 면이 0인지 아닌지만 판단하면 되기 때문이다.

 

 

정의

ch[MAX][MAX] : 치즈값을 저장하는 2차원 배열, 상태에 따라 다른 상수를 저장하고 있다.

0 : 내부

2 : 외부

1 : 치즈

3 : 녹을 치즈

 

check 함수

: 남아있는 치즈(상태가 1인 변수)가 있는지 없는지 확인하는 함수

 

bfs 함수

: 외부와 내부를 구별해주는 함수이다. 

외부를 명확히 정의하기 위해 입력값을 1부터 N, M 까지의 인덱스만 사용하여 저장했다.

따라서 0과 N+1, M+1 인덱스는 항상 비워두도록 만들었다. (아래 사진 참고)

 

 

이렇게 하게 되면 (0,0)은 무조건 외부가 된다.

따라서 (0,0)에서 bfs를 실행시켜 0인 값을 탐색한다면 방문하는 곳이 곧 외부가 된다.

외부임을 표시하기 위해 2를 저장시켰다.

 

외부와 내부가 구별되었다면 그 후에는 간단하다.

ch 배열에서 1(치즈)인 값을 순차적으로 찾아 접하는 면의 값이 2(외부)인지를 확인하면 된다.

 

만약 접하는 면이 2인 횟수가 2회를 넘어가면 해당 치즈는 이번 턴에 녹아야 할 치즈이다.

하지만 해당 값을 0으로 바꾸면 시간을 구분시키기 어렵다.

잘못하면 첫번째 시간에 모든 치즈가 다 녹을 수도 있기 때문이다.

여기서 말하는 시간은 결과로 출력해야 하는 시간을 말한다.

 

따라서 임의로 3(녹을 치즈 의미)이라는 값을 저장했다.

 

다음 시간으로 넘어가면 다시 bfs를 (0,0) 에서 시작하여 1(치즈)가 아닐경우엔 계속 탐색한다.

다시 말해, 외부 공간을 다시 탐색해서 2(외부를 의미)를 저장시키는 과정이다.

 

이렇게 계속 반복하게 된다면 ch 배열에 1이 모두 없어지기 때문에 그 시간을 출력하면 정답이다.

 

 

최종 코드

#include <iostream>
#include <queue>
#include <cstring>

#define MAX 102
using namespace::std;

//0: 내부
//2: 외부
//1: 치즈
//3: 녹을 치즈

int ch[MAX][MAX];
int N, M;
int sec;
int visited[MAX][MAX];

int ud[4] = {-1,1,0,0};
int lr[4] = {0,0,-1,1};

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

int bfs(int y, int x, int check){
    queue<pair<int, int>> q;
    q.push({y, x});
    visited[y][x] = 1;
    ch[y][x] = check;
    
    
    while(!q.empty()){
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        
        if(ty == N+1 && tx == M+1){  // 외부공기 조건
            return 1;
        }
        
        for(int i=0; i<4; i++){
            int ny = ty + ud[i];
            int nx = tx + lr[i];
            if(ny>=0 && nx>=0 && ny<=N+1 && nx<=M+1){
                if(visited[ny][nx] == 0){
                    if(ch[ny][nx] != 1){
                        ch[ny][nx] = check;
                        visited[ny][nx] = 1;
                        q.push({ny, nx});
                    }
                }
            }
        }
    }
    return 0;  // 내부
}

int main(){
    scanf("%d %d", &N, &M);
    
    for(int i=1; i<=N; i++){
       for(int j=1; j<=M; j++){
            scanf("%d", &ch[i][j]);
        }
    }

    
    while(check()){
        memset(visited, 0, sizeof(visited));
        
        bfs(0,0,2);  // 외부 만들기
        
        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
                if(ch[i][j] == 1){
                    int cnt = 0;
                    
                    for(int k=0; k<4; k++){
                        int ty = i+ud[k];
                        int tx = j+lr[k];
                        if(ch[ty][tx] == 2) // outside
                            cnt++;
                    }
                    
                    if(cnt >= 2)
                        ch[i][j] = 3;
                }
            }
        }
        sec++;
    }
    
    cout << sec << '\n';
}

 

 

잡담

시간은 걸렸지만 그래도 골드를 슬슬 풀어가고 있다.