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

 

2638번: 치즈

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

www.acmicpc.net

2636번과 매우 유사한 문제입니다.

2636번과 다른점은 적어도 2변 이상이 공기와 인접해야 치즈가 녹는다는 점입니다.

가장자리에는 치즈가 없기때문에 0,0에서 bfs로 공기부분을 체크하고

반복문으로 치즈가 공기와 인접하는지 확인하고 2변 이상이 인접하면 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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int list[100][100], N, M;
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
bool visit[100][100];
 
void bfs() {
    memset(visit, false, sizeof(visit));
 
    queue<pair<int, int> > q;
    q.push({ 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 + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (visit[nx][ny] || list[nx][ny]) continue;
 
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!list[i][j]) continue;
 
            int cnt = 0;
            for (int x = 0; x < 4; x++) {
                int ni = i + direct[x][0];
                int nj = j + direct[x][1];
 
                if (visit[ni][nj]) cnt++;
            }
 
            if (cnt >= 2) list[i][j] = 0;
        }
    }
}
 
bool chk() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (list[i][j]) return true;
        }
    }
 
    return false;
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    for (int ans = 1; ; ans++) {
        bfs();
        func();
        if (!chk()) {
            cout << ans << '\n';
            break;
        }
    }
 
    return 0;
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 16956 늑대와 양  (0) 2021.02.03
boj 20419 화살표 미로 (Easy)  (0) 2021.01.23
boj 17142 연구소 3  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22

+ Recent posts

티스토리툴바