[BFS] 2638번 치즈

2638번 치즈

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

 

문제

N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

 

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

 

예제 입력

8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

 

예제 출력

4

 

해결방법

BFS 탐색과 완전 탐색을 순차적으로 수행하여 해결하는 문제이다

 

• 1) 가장 자리는 무조건 공기층
• 2) 가장 자리(0,0) 에서 BFS 탐색하여 외부 공기 부분 -1로 변경
• 3) -1 : 외부 공기, 0: 내부 공기, 1: 치즈
• 4) 가장자리를 제외한 노드를 탐색하여 치즈인 부분의 4변 중 2변이 -1 이라면 녹을 예정
• 5) 벡터로 저장한 다음 한번에 녹임
• 6) -1인 외부 공기 부분을 다시 0으로 reset
• 7) flag 를 둬서 녹일 치즈가 있다면 ans++, 치즈가 없다면 break

 

 

⭐️Solution⭐️

이 문제의 솔루션은 외부 공기와 내부 공기를 나눠 생각하는 것이다

처음에는 이 부분을 생각하지 못해서 많이 헤맸지만 한 블로그의 솔루션을 참조했다

이러한 유형의 다른 문제가 있으면 꼭 풀어봐야겠다!!

 

+ 추가 학습을 통해 다른 풀이를 적용했다

1. 가장자리는 모두 공기라는 조건으로 (0,0) 좌표부터 BFS 탐색을 진행한다
2. 공기라면 그대로 탐색을, 치즈라면 air배열의 값을 +1 시켜준다
3. 만약 air의 값이 2를 넘어서면 방문처리를 해준 뒤, melted 벡터에 넣어준다
4. BFS 탐색이 끝났다면, melted 벡터의 값을 큐에 다시 넣어준다
5. 이를 반복하다가 녹는 치즈가 없다면 반복문을 종료한다

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 101
#define INF 987654321
using namespace std;

typedef pair<int, int> node;

int n,m,ans;
bool flag;
int map[MAX][MAX];
bool visit[MAX][MAX];

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

vector<node> melted;

void bfs(){
    queue<node> q;
    q.push(node(0,0));
    visit[0][0] = true;
    
    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(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            if(visit[nx][ny]) continue;
            
            if(map[nx][ny] == 0){
                q.push(node(nx,ny));
                visit[nx][ny] = true;
            }
        }
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(visit[i][j]){
                map[i][j] = -1;
            }
        }
    }
}

void chk_melted(){
    for(int i=1; i<n-1; i++){
        for(int j=1; j<m-1; j++){
            if(map[i][j] == 1){
                int cnt = 0;
                flag = true;
                for(int k=0; k<4; k++){
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    
                    if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
                    if(map[nx][ny] == -1) cnt++;
                }
                if(cnt >= 2) melted.push_back(node(i,j));
            }
        }
    }
}

void go_melted(){
    // melt
    for(int i=0; i<melted.size(); i++){
        int x = melted[i].first;
        int y = melted[i].second;
        map[x][y] = 0;
    }
    
    // reset
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(map[i][j] == -1){
                map[i][j] = 0;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
        }
    }
    
    ans = 0;
    while(true){
        // 치즈가 전부 녹을 때 까지 무한 루프
        flag = false;
        memset(visit, false, sizeof(visit));
        melted.clear();
        bfs();
        chk_melted();
        go_melted();
        
        if(flag) ans++;
        else break;
    }
    cout << ans << endl;
}

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

typedef pair<int,int> node;

int n,m,ans;
int map[MAX][MAX];
int air[MAX][MAX];
bool visited[MAX][MAX];

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

queue<node> q;
vector<node> melted;

void printMap(){
    cout << "\n";
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

void bfs(){
    q.push(node(0,0));
    visited[0][0] = true;
    
    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(nx<0 || ny<0 || nx>=n || ny>=m) continue;
            
            // 공기라면
            if(map[nx][ny] == 0 && !visited[nx][ny]){
                q.push(node(nx,ny));
                visited[nx][ny] = true;
            }
            // 치즈라면
            else if(map[nx][ny] == 1){
                air[nx][ny] += 1;
                
                // 치즈가 녹을 예정이면?
                if(air[nx][ny] >= 2 && !visited[nx][ny]){
                    melted.push_back(node(nx,ny));
                    visited[nx][ny] = true;
                }
            }
        }
        
        if(q.empty()){
            if(!melted.empty()) ans++;
            else break;
            
            for(int i=0; i<melted.size(); i++){
                q.push(melted[i]);
                map[melted[i].first][melted[i].second] = 0;
            }
            melted.clear();
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
        }
    }
    
    memset(visited, false, sizeof(visited));
    ans = 0;
    bfs();
    
    cout << ans << "\n";
    return 0;
}