Algorithm/BOJ

[백준 2636] 치즈 C++

Henu 2021. 7. 1. 14:22
 

2636번: 치즈

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진

www.acmicpc.net

BFS

1. 문제 해결 아이디어

 

치즈의 겉 표면을 찾기 위한 BFS + 겉표면을 녹이는 BFS

이렇게 2개의 BFS를 사용해서 풀었다.

 

BFS를 2개 쓴거라서 아마 내 풀이가 최적의 풀이는 절대 아닐거라 생각한다.

 

 

먼저 공기와 맞닿아 있는 치즈표면을 BFS를 통해서 모두 구하면서 개수를 저장해 놓는다.

이때 치즈가 없다면 종료

만약 치즈가 있다면 겉표면 치즈들을 녹이는 BFS를 수행한다.

 

두 과정을 합칠 수 있을것 같다..

2. 코드

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <queue>
#include <cstring>
 
#define pii pair<int, int>
 
using namespace std;
 
int Map[101][101];
int N, M;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
 
void input(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> Map[i][j];
        }
    }
}
 
bool melt_surface(){
    int cheese_num = 0;
    queue< pii > temps;
    bool visited[101][101];
    memset(visited, 0, sizeof(visited));
    
    temps.push({0, 0});
    visited[0][0] = true;
    
    while(!temps.empty()){
        pii now = temps.front();
        temps.pop();
        
        for(int k = 0; k < 4; k++){
            int nr = now.first + dr[k];
            int nc = now.second + dc[k];
            if(nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc]) continue;
            
            visited[nr][nc] = true;
            if(Map[nr][nc]){
                cheese_num++;
                Map[nr][nc] = 0;
                continue;
            }
            else temps.push({nr, nc});
        }
    }
    if(cheese_num) return true;
    else return false;
}
 
bool cvisited[101][101];
 
int cheese_block(int r, int c){
    int block_cnt = 1;
    queue< pii > que;
    cvisited[r][c] = true;
    que.push({r, c});
    
    while(!que.empty()){
        pii now = que.front();
        que.pop();
        
        for(int k = 0; k < 4; k++){
            int nr = now.first + dr[k];
            int nc = now.second + dc[k];
            if(nr < 0 || nr >= N || nc < 0 || nc >= M || cvisited[nr][nc] || !Map[nr][nc]) continue;
            
            block_cnt++;
            cvisited[nr][nc] = true;
            que.push({nr, nc});
        }
    }
    
    return block_cnt;
}
 
// void show(){
//     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 solve(){
    int result = 0, time = 0;
    
    while(true){
        int block_cnt = 0;
        memset(cvisited, 0, sizeof(cvisited));
        
        for(int i = 0; i < N; i++){
            for(int j = 0 ; j < M; j++){
                if(cvisited[i][j] || !Map[i][j]) continue;
                block_cnt += cheese_block(i, j);
            }
        }
        if(!block_cnt) break;
        result = block_cnt;
        
        melt_surface();
        time++;
    }
    
    cout << time << "\n" << result;
}
 
int main(){
    input();
    solve();
    return 0;
}
 cs