[BOJ][C++] 백준 2636번: 치즈

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

2636번: 치즈

 

문제

 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다.

판의 가장자리에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다.

치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다.

치즈의 구멍을 둘러싼 치즈는 녹지 않는다.

다시 한 시간 후에는 녹아 없어지고 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다.

그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다.

치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

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

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다.

세로와 가로의 길이는 최대 100이다.

판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.

치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고,

둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

 

풀이

보드에 표시할 건 네가지

1: 치즈, 2: 녹을 예정인 치즈, 3: 외부 공기, 0: 내부 공기

 

다음 단계로 진행된다

1. 외부와 접촉된 공기(0)들을 외부 공기(3)로 바꾼다

2. 치즈(1)중 외부공기(3)과 접촉한 치즈들만 녹을 예정인 치즈(2)로 바꿔준다

3. 녹을 예정인 치즈(2)들을 녹여서 빈 자리(0)로 바꾼다

 

2번과 3번 과정을 동시에 할 경우(찾자마자 녹여버릴 경우)

같은 시간에 사라진 다른 치즈의 영향을 받아

없어지지 않아도 될 치즈까지 없어질 수 있으므로 따로 진행해줘야한다.

 

1번의 경우 0인 부분을 찾아 dfs를 진행하여 인접한 0들을 3으로 바꿔주면 된다.

 

예를 들어, 주어진 예제에 대해서는 다음과 같이 진행된다

// 시간0
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 1 1 3 3 3 
3 1 1 1 3 3 3 1 1 3 3 3 
3 1 1 1 1 1 1 3 3 3 3 3 
3 1 1 1 1 1 0 1 1 3 3 3 
3 1 1 1 1 0 0 1 1 3 3 3 
3 3 1 1 0 0 0 1 1 3 3 3 
3 3 1 1 1 1 1 1 1 3 3 3 
3 3 1 1 1 1 1 1 1 3 3 3 
3 3 1 1 1 1 1 1 1 3 3 3 
3 3 1 1 1 1 1 1 1 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 

// 시간1
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 1 1 3 3 3 3 3 3 3 3 
3 3 1 1 1 1 3 3 3 3 3 3 
3 3 1 1 1 3 3 1 3 3 3 3 
3 3 3 1 3 3 3 1 3 3 3 3 
3 3 3 1 1 1 1 1 3 3 3 3 
3 3 3 1 1 1 1 1 3 3 3 3 
3 3 3 1 1 1 1 1 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 

// 시간2
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 1 3 3 3 3 3 3 3 3 
3 3 3 1 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 1 1 1 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 

// 시간3
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3 3 3 3 3

 

코드

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> ci;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

void dfs(vector<vector<int>>&board, int i, int j, int r, int c) {
    if(i<0 || i>=r || j<0 || j>=c) return;
    if(board[i][j] != 0) return;
    
    board[i][j] = 3;
    
    for(int dir=0; dir<4; dir++) {
        int x = i+dx[dir];
        int y = j+dy[dir];
        
        dfs(board, x, y, r, c);
    }
}

ci solution(vector<vector<int>>&board, int r, int c, int cheese) {
    int _time = 0, prevCheese = 0;
    dfs(board, 0, 0, r, c); // 외부 공기 3으로 바꾸기
    while(true) {
        if(cheese==0) {
            break;
        }
        
        // 1시간 전 치즈 갯수 저장
        prevCheese = cheese;
        
        // 치즈(1)들 중 외부공기(3)와 접촉했으면 녹을 대상(2)로 표시하기
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(board[i][j]!=1) {
                    continue;
                }
                for(int dir=0; dir<4; dir++) {
                    int x = i + dx[dir];
                    int y = j + dy[dir];
                    if(board[x][y]==3) {
                        board[i][j] = 2;
                    }
                } 
            }
        }
        
        // 녹을 치즈(2)들 녹이기
        vector<ci> melted;
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(board[i][j]==2) {
                    board[i][j] = 0;
                    cheese--;
                    melted.push_back({i,j});
                }
            }
        }
        
        // 노출된 내부공기(0) 외부공기로 바꾸기(3)
        for(ci i : melted) {
            dfs(board, i.first, i.second, r, c);
        }
        
        // 시간 증가
        _time++;
    }
    
    return {_time, prevCheese};
}

int main() {
    // 입력
    int r, c, cheese=0;
    cin >> r >> c;
    vector<vector<int>> board(r, vector<int>(c));
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            int input;
            cin >> input;
            if(input == 1) {
                cheese++;
            }
            board[i][j] = input;
        }
    }

    // 출력
    ci answer = solution(board, r, c, cheese);
    cout << answer.first << "\n" << answer.second;
    
    return 0;
}