[Baekjoon] 치즈

숨숨숨 2021. 3. 15. 20:50

👀 문제 설명

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

예제 입력 1

13 12

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 1 0 0 0

0 1 1 1 0 0 0 1 1 0 0 0

0 1 1 1 1 1 1 0 0 0 0 0

0 1 1 1 1 1 0 1 1 0 0 0

0 1 1 1 1 0 0 1 1 0 0 0

0 0 1 1 0 0 0 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

예제 출력 1

✍🏻풀이

외부 공기와 닿아있는 치즈들을 찾아 녹여나가면 되는 문제이다.

문제는, 현재 위치의 치즈가 외부 공기와 닿아있는지 어떻게 확인하냐는 것이다.

BFS 문제로, 큐를 사용해서 풀면 되는데, 처음에는 큐에 외부 공기와 닿아있는 치즈의 위치들을 넣으려 했다.

하지만 이렇게 할 경우, 옆에 닿은 공기가 외부 공기인지, 내부 공기인지 파악할 수 없는 문제가 발생한다.

<치즈를 녹이는 함수 removeCheese>

해결책은 큐에 치즈의 위치가 아닌, 외부 공기의 위치를 넣는 것이었다.

외부 공기의 위치를 저장해두기 위해 2차원 배열 outsideAir을 모두 0으로 초기화한다.

-> 이 때, 2차원 배열을 0으로 초기화하기 위한 함수는 cstring 헤더에 존재하는 memset 함수를 사용한다.

memset(outsideAir, 0, sizeof(outsideAir));

먼저, (0, 0)부터 시작해서 상하좌우를 모두 탐색한다. 만약 탐색한 위치에 치즈가 있다면 다음으로 넘어간다. (이렇게 할 경우, 치즈의 상하좌우는 탐색하지 않게 되므로 자연스레 치즈와 내부 공기는 탐색하지 않게 된다.)

그리고 해당 위치가 외부 공기라면, outsideAir 배열을 사용해 외부 공기라고 표시해준다.

큐가 비면, while문을 빠져나오고, (1, 1)부터 (H - 2, W - 2)까지 탐색하며 해당 위치가 치즈가 있는 곳이고, 인접한 곳이 외부 공기라면 치즈를 녹여준다.

main 함수에서는 while문을 사용해 치즈가 다 녹을때까지 치즈를 녹여주면 된다.

치즈를 녹이는 함수를 실행하기 전에, 현재 치즈의 개수를 curCheese 변수에 저장하고, 만약 curCheese가 0. 즉, 치즈가 다 녹았다면 while문을 빠져나온다.

치즈가 다 녹지 않았다면, lastCount 변수에 curCheese를 저장해 치즈가 녹기 직전의 치즈 수를 저장하도록 한다.

그리고 치즈를 녹이는 함수 removeCheese()를 실행하고, 치즈가 다 녹는데 걸리는 시간을 계산하기 위해 time에 1을 더한다.

코드

#include <stdio.h>
#include <iostream>
#include <queue>
#include <cstring> // memset 함수가 속한 헤더

#define MAX 100

using namespace std;

int rectangle[MAX][MAX];
int outsideAir[MAX][MAX]; // 해당 위치가 바깥쪽의 공기인지 담고 있는 배열
// 위, 오른쪽, 아래, 왼쪽
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int H, W;

// 치즈수를 세는 함수
int countCheese() {
    int count = 0;
    
    // 가장자리에는 치즈가 있지 않다.
    for (int i = 1; i < H - 1; i++) {
        for (int j = 1; j < W - 1; j++) {
            if (rectangle[i][j] == 1) {
                count++;
            }
        }
    }
    
    return count;
}

void removeCheese() {
    queue<pair<int, int>> Q; // 외부 공기들의 위치를 담는 큐
    memset(outsideAir, 0, sizeof(outsideAir)); // !! 2차원 배열 outsideAir을 모두 0으로 초기화시킨다 !! -> 매번 치즈를 녹일때마다 초기화해줘야 한다.
    
    Q.push({ 0, 0 });
    outsideAir[0][0] = 1;
    
    while (!Q.empty()) {
        int curX = Q.front().first;
        int curY = Q.front().second;
        Q.pop();
        
        for (int dir = 0; dir < 4; dir++) {
            int nextX = curX + dx[dir];
            int nextY = curY + dy[dir];
            
            if (nextX < 0 || nextX >= H || nextY < 0 || nextY >= W) // 범위를 벗어나면 다음으로 넘긴다
                continue;
            
            if (outsideAir[nextX][nextY] == 1) // 이미 방문했을 경우 다음으로 넘긴다
                continue;
            
            if (rectangle[nextX][nextY] == 1) // 해당 위치에 치즈가 있다면 다음으로 넘긴다
                continue;
            
            Q.push({ nextX, nextY });
            outsideAir[nextX][nextY] = 1;
        }
    }
    
    for (int i = 1; i < H - 1; i++) {
        for (int j = 1; j < W - 1; j++) {
            if (rectangle[i][j] == 0) // 치즈가 아닐 경우 다음으로 넘긴다.
                continue;
            
            for (int dir = 0; dir < 4; dir++) { // 인접한 곳 확인
                int nextX = i + dx[dir];
                int nextY = j + dy[dir];
                
                if (outsideAir[nextX][nextY] == 1) { // 인접한 곳에 바깥 공기가 있으면 치즈를 녹인다
                    rectangle[i][j] = 0;
                    break; // break를 해야 다음의 불필요한 연산을 하지 않는다
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    
    // input
    cin >> H >> W;
        
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> rectangle[i][j];
        }
    }
    
    // solve
    int time = 0;
    int lastCount = 0;
    
    while (true) {
        int curCheese = countCheese();
        
        if (curCheese == 0) // 치즈가 다 녹으면 while문을 빠져나온다.
            break;
        
        lastCount = curCheese; // 다음 치즈를 녹이기 전 단계의 치즈의 수
        removeCheese();
        time++; // 치즈가 다 녹는데 걸리는 시간
    }
    
    cout << time << "\n";
    cout << lastCount << "\n";
    
    return 0;
}