(C++) - 백준(BOJ) 2636번 : 치즈

www.acmicpc.net/problem/2636

2636번: 치즈

bfs문제였습니다.

 

풀이방법

 1. 판의 테두리는 0이 보장되므로 0,0지점은 0이라고 할 수 있습니다.

 

 2. 입력을 받고, 모두 녹을 때까지 loop를 돕니다.

   2-1. 먼저 치즈칸의 개수를 cnt변수에 저장합니다.

   2-2. 외부공기임을 표시하기 위해 checkAir함수를 시행합니다. 이는 0,0부터 시작해 bfs를 시행해 모든 외부공기 칸을 -1로 만들어줍니다.

   2-3. bfs를 시행합니다. 이는 외부공기와 맏닿아있는 치즈를 녹여줍니다.

   2-4. 판을 갱신해줍니다.

   2-5. 시간을 1증가해줍니다.

 

 3. 시간과 녹기 한 시간전의 치즈 칸의 개수를 출력해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n, m, hour, cnt;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int board[101][101],ck[101][101],ckAir[101][101], boardCopy[101][101], air[101][101];

bool isNotMelt(){
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(board[i][j]) return 1;
    return 0;
}

int getCheeseArea(){
    int cnt = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(board[i][j])cnt++;
    return cnt;
}

void updateBoard(){
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            board[i][j] = boardCopy[i][j];
}

void checkAir(int i, int j){
    queue <pii> q;
    q.push({i,j});
    ckAir[i][j] = 1;
    board[i][j] = -1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= n || 0 > ny || ny >= m) continue;
            if(board[x][y]<=0 && board[nx][ny]!=1) board[nx][ny] = -1;
            if(ckAir[nx][ny] || board[nx][ny] == 1) continue;
            ckAir[nx][ny] = 1;
            q.push({nx,ny});
        }
    }
}

void bfs(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(!ck[i][j] && board[i][j]){
                queue <pii> q;
                q.push({i,j});
                ck[i][j] = 1;
                while(!q.empty()){
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    boardCopy[x][y] = board[x][y];
                    for(int i = 0; i < 4; i++){
                        int nx = x + dx[i];
                        int ny = y + dy[i];
                        if(0 > nx || nx >= n || 0 > ny || ny >= m) continue;
                        if(board[nx][ny] < 0) boardCopy[x][y] = 0;
                        if(ck[nx][ny]) continue;
                        ck[nx][ny] = 1;
                        q.push({nx,ny});
                    }
                }
            }
        }
    }
}


int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> board[i][j];

    while(isNotMelt()){
        memset(ckAir,0,sizeof(ckAir));
        memset(ck,0,sizeof(ck));
        memset(boardCopy,0,sizeof(boardCopy));
        cnt = getCheeseArea();
        checkAir(0,0);
        bfs();
        updateBoard();
        hour++;
    }
    cout << hour << '\n' << cnt;
}