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

 

2638번: 치즈

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

www.acmicpc.net

앞에서 풀었던 2636번 치즈 (풀이 링크)문제와 비슷한 문제이다.

다른 점은 4 변 중 2 변 이상이 공기에 접촉해야 치즈가 놓는다.

답도 시간만 출력하면 된다.

 

 

앞의 문제와 마찬가지로 테두리에는 치즈가 없으므로

(0,0)을 먼저 큐에 넣어 바깥 영역을 먼저 bfs로 구하고

치즈가 두번 이상 바깥 영역(공기 부분)과 접촉해있다면 치즈가 녹는다(0이 된다).

 

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
119
#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int r, c;
int board[100][100];
bool check[100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
 
//치즈수를 카운트
int countCheese() {
    int cnt = 0;
    for (int i = 1; i < r - 1; i++) {
        for (int j = 1; j < c - 1; j++) {
            if (board[i][j] == 1) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
 
 
void solve() {
 
    //bfs로 바깥 영역을 체크
    queue<pair<int, int>> q;
    memset(check, false, sizeof(check));
    int x = 0;
    int y = 0;
 
    q.push(make_pair(x,y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            if (check[nx][ny]) continue;
            if (board[nx][ny] == 1) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;;
        }
    }
 
 
 
    for (int i = 1; i < r-1; i++) {
        for (int j = 1; j < c-1; j++) {
            if (board[i][j] == 0) continue;
 
            
            int cnt = 0;
            //네방향을 검사
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                if (check[nx][ny]) {
                    //공기에 접촉하는 횟수
                    cnt++;
                }
            }
 
 
            //두 변 이상 공기에 접촉하면 녹는다.
            if (cnt >= 2) {
                board[i][j] = 0;
            }
        }
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
 
    int time = 0;
    while (true) {
        int tmp = countCheese();
 
        //치즈가 모두 녹으면 break
        if (tmp == 0) {
            break;
        }
    
        solve();
        time++;
    }
 
    cout << time << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1987. 알파벳  (0) 2019.07.11
[BOJ] 7562. 나이트의 이동  (0) 2019.07.09
[BOJ] 2636. 치즈  (0) 2019.07.08
[BOJ] 1347. 미로 만들기  (0) 2019.07.06
[BOJ] 14620. 꽃길  (0) 2019.07.06

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

 

2636번: 치즈

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가

www.acmicpc.net

한 시간마다 공기랑 접촉한 치즈는 녹게 되는데

모든 치즈가 녹아 없어지는 데 걸리는 시간과

한 시간 전에 남아있는 치즈 조각이 놓여있는 칸의 개수를 구하는 문제다.

 

처음에 바깥 부분과 치즈 가운데 구멍을 어떻게 구분할지 고민하다가

가장자리에는 치즈가 놓여 있지 않는다는 문제 조건을 보고

가장자리부터 시작해서 연결된 영역(치즈가 아닌 바깥 영역)을 구하면 되겠다고 생각했다.

 

처음에 (0,0)부터 큐에 넣고 bfs를 시작하면 바깥공기 영역이 모두 체크된다.

그럼 이제 이 체크된 영역에 인접해 있는 치즈를 없애주면 된다(0으로 만들어 준다).

매시간마다 치즈 수를 세어주고 이전의 치즈수를 저장해둔다.

현재 치즈수가 0이 되면 반복문을 빠져나와  걸린 시간과 이전의 치즈 수 출력해주면 된다.

 

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
119
120
121
122
123
124
125
#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int r, c;
int board[100][100];
bool check[100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
//치즈수를 센다
int countCheese() {
    int cnt = 0;
    for (int i = 1; i < r - 1; i++) {
        for (int j = 1; j < c - 1; j++) {
            if (board[i][j] == 1) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
 
 
void solve() {
 
    //bfs로 바깥 영역을 체크
    queue<pair<int, int>> q;
    memset(check, false, sizeof(check));
    int x = 0;
    int y = 0;
 
    q.push(make_pair(x,y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            //범위 체크
            if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            
            //방문 체크
            if (check[nx][ny]) continue;
            
            //치즈인 경우 skip
            if (board[nx][ny] == 1) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;;
        }
    }
 
 
 
    //바깥영역과 닿아있는 치즈는 녹는다.
    for (int i = 1; i < r-1; i++) {
        for (int j = 1; j < c-1; j++) {
            //치즈 아닌부분 skip
            if (board[i][j] == 0) continue;
 
 
            //상하좌우 중 하나라도 밖이랑 닿아있으면 녹는다.
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (check[nx][ny]) {
                    board[i][j] = 0;
                    break;
                }
            }
        }
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
 
    int cheeseCnt= 0;
    int time = 0;
    int lastcnt = 0;
    while (true) {
        int tmp = countCheese();
 
 
        //치즈가 다 녹을 떄까지 반복
        if (tmp == 0) {
            break;
        }
        else {
            lastcnt = tmp;
        }
        
        solve();
        time++;
    }
 
    cout << time << '\n';
    cout << lastcnt << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 7562. 나이트의 이동  (0) 2019.07.09
[BOJ] 2638. 치즈  (0) 2019.07.08
[BOJ] 1347. 미로 만들기  (0) 2019.07.06
[BOJ] 14620. 꽃길  (0) 2019.07.06
[BOJ] 14889. 스타트와 링크  (0) 2019.07.06

+ Recent posts

티스토리툴바