백준 2636번 치즈 (C++)

문제 링크 : www.acmicpc.net/problem/2636

2636번: 치즈

이 문제의 관건은 다음과 같다.

위 이미지에 표시된 치즈 내부에 있는 구멍과 외부 공기를 구분하는 것이다.

 

문제 풀이는 다음과 같다.

1. 먼저 아래코드는 공기와 접촉된 모든 치즈들을 녹이는 코드이다.

대략적으로 훑어보고 다음 차례에서 세세한 설명을 이해해보자.

    while(true){
        done = false;
        cheese = 0;
        outofcheese(1,1); // 치즈 밖의 공기들만 별도로 표시해주는 함수
        queue<pair<int,int>> q;
        for(int i=1; i<=h; i++){ // 공기와 맞닿은 치즈들만 큐에 넣는 부분
            for(int j=1; j<=w; j++){
                if(arr[i][j]==0&&visited[i][j]==true){
                    y=i;
                    x=j;
                    for(int i=0; i<4; i++){
                        ny = y+my[i];
                        nx = x+mx[i];
                        if(ny>=1&&ny<=h&&nx>=1&&nx<=w&&arr[ny][nx]==1&&!ch[ny][nx]){
                            ch[ny][nx] = true;
                            q.push({ny,nx});
                        }
                    }
                }
            }
        }
        while(!q.empty()){ // 공기와 맞닿은 치즈들을 공기로 체크해주는 과정
            y = q.front().first;
            x = q.front().second;
            arr[y][x] = 0;
            cheese++;
            done = true;
            q.pop();
        }
        if(done){
            cnt++;
            ans = cheese;
        }
        else break;
        memset(ch,false,sizeof(ch));
        memset(visited,false,sizeof(visited));
    }

2. 다음 코드는 위의 while문의 최상단 부분이다.

    while(true){
        done = false;
        cheese = 0;
        outofcheese(1,1);

보다시피 while문은 true로 반복되는데, 결국 치즈가 모두 녹아내릴때까지 진행되어야 하기 때문이다.

이때 치즈가 모두 녹아서 while문을 빠져나올 분기점은 done이라는 bool문으로 결정된다.

여기서 주의할 것은 outofcheese(1,1)이라는 함수다.

1,1은 최초의 공기좌표를 의미하는데, 문제에서 배열의 모든 모서리가 공기라고 선언했기 때문에 1,1부터 시작해도 무방하다.

.

3. 아래는 outofcheese 함수의 코드이다.

void outofcheese(int yy, int xx){
    visited[yy][xx] = true;
    for(int i=0; i<4; i++){
        ny = yy+my[i];
        nx = xx+mx[i];
        if(ny>0&&ny<=h&&nx>0&&nx<=w&&!visited[ny][nx]&&arr[ny][nx]==0) outofcheese(ny,nx);
    }
}

y좌표와 x좌표를 인자값으로 받고 해당 위치의 visited함수를 true로 바꿔준다.

또한 해당 좌표를 기준으로 4방위를 둘러보았을때 공기가 있을 경우, 해당 지점으로 또다시 outofcheese를 진행해준다.

이때 한 번 방문한 곳을 다시 방문하지 않도록 조건에 !visited[ny][nx]를 적어주는것을 잊지말자.

 

이렇게 진행하면 치즈 외부에 있는 공기들을 별도로 표시할수 있게된다.

 

4. 다음은 공기와 맞닿은 치즈들의 좌표를 큐에 넣어주는 과정이다.

        queue<pair<int,int>> q;
        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++){
                if(arr[i][j]==0&&visited[i][j]==true){ // 1
                    y=i;
                    x=j;
                    for(int i=0; i<4; i++){
                        ny = y+my[i];
                        nx = x+mx[i];
                        if(ny>=1&&ny<=h&&nx>=1&&nx<=w&&arr[ny][nx]==1&&!ch[ny][nx]){ // 2
                            ch[ny][nx] = true;
                            q.push({ny,nx});
                        }
                    }
                }
            }
        }

1차적으로 해당 지점이 공기이며, 외부공기에 해당될 경우 통과된다.

2차적으로 해당 지점을 기준으로 4방면의 지점이 치즈이면서 아직 방문하지 않은 곳일 경우, 방문표시를 해줌과 동시에 큐에 넣어준다.

 

5. 다음은 큐에 넣어준 공기와 맞닿은 치즈들을 모두 0 = 공기로 바꿔주는 과정이다.

        while(!q.empty()){
            y = q.front().first;
            x = q.front().second;
            arr[y][x] = 0;
            cheese++;
            done = true;
            q.pop();
        }

만약 이 과정을 한 번이라도 거쳤다면 치즈를 녹이는 과정이 진행되었다는 뜻이므로, done을 true로 표시해준다.

 

6. 다음은 치즈의 넓이를 구함과 동시에 while문을 종료할지 판단하는 코드이다.

        if(done){
            cnt++;
            ans = cheese;
        }
        else break;
        memset(ch,false,sizeof(ch));
        memset(visited,false,sizeof(visited));
    }

만약 한 번이라도 치즈를 녹였다면 done은 true가 된다. 

때문에 카운트 횟수를 +1 증가시키고, 녹였던 치즈의 사이즈를 정답 변수에 저장해준다.

반대로 한 번이라도 치즈를 녹이지 않았다면 이미 모든 치즈가 녹아서 진행할 일이 없었다는 뜻이므로 while문을 빠져나오면 된다.

마지막으로 치즈를 녹인 후 또 다시 치즈를 녹이기 위해 사용했던 ch배열과 visited배열을 false로 초기화해주는 것을 잊으면 안된다.

 

7. 정답을 출력한다.

 

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 101
using namespace std;

int arr[MAX][MAX], h,w,my[] = {-1,0,1,0}, mx[] = {0,1,0,-1}, ny, nx, y, x, cnt = 0, ans = 0, cheese = 0;
bool ch[MAX][MAX], visited[MAX][MAX], done;

void outofcheese(int yy, int xx){
    visited[yy][xx] = true;
    for(int i=0; i<4; i++){
        ny = yy+my[i];
        nx = xx+mx[i];
        if(ny>0&&ny<=h&&nx>0&&nx<=w&&!visited[ny][nx]&&arr[ny][nx]==0) outofcheese(ny,nx);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> h >> w;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++) cin >> arr[i][j];
    }
    while(true){
        done = false;
        cheese = 0;
        outofcheese(1,1);
        queue<pair<int,int>> q;
        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++){
                if(arr[i][j]==0&&visited[i][j]==true){
                    y=i;
                    x=j;
                    for(int i=0; i<4; i++){
                        ny = y+my[i];
                        nx = x+mx[i];
                        if(ny>=1&&ny<=h&&nx>=1&&nx<=w&&arr[ny][nx]==1&&!ch[ny][nx]){
                            ch[ny][nx] = true;
                            q.push({ny,nx});
                        }
                    }
                }
            }
        }
        while(!q.empty()){
            y = q.front().first;
            x = q.front().second;
            arr[y][x] = 0;
            cheese++;
            done = true;
            q.pop();
        }
        if(done){
            cnt++;
            ans = cheese;
        }
        else break;
        memset(ch,false,sizeof(ch));
        memset(visited,false,sizeof(visited));
    }
    cout << cnt << "\n" << ans << "\n";
    return 0;
}

분명히 어려운 문제가 아니였다. 하지만 컨디션 관리를 못한 탓에 두통이 밀려와 제한 시간내에 풀지 못했다.

건강관리가 중요하다는 것을 깨닫게 해준 문제였다.