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

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

 

2636번: 치즈

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

www.acmicpc.net

판의 가장자리에는 치즈가 없기 때문에 0,0에서 bfs로 탐색하여 공기 부분을 체크를 합니다.

그 후에 반복문으로 치즈가 있는 위치에 인접한 좌표에 공기가 있으면 0으로 바꿔줍니다.

이 과정을 반복하여 치즈가 모두 녹아 없어지는 데 걸린 시간을 구하면서 1시간 전에 남아있는 치즈조각의 갯수를 출력합니다.

(치즈를 한번 녹였을 때 남아있는 치즈조각의 갯수를 계속해서 갱신합니다.)

 

 

[C++]

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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int list[100][100], N, M, pre, ans;
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 (list[nx][ny] || visit[nx][ny]) continue;
 
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void func() {
    ans = pre;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            if (!list[i][j]) continue;
 
            for (int k = 0; k < 4; k++) {
                int nx = i + direct[k][0];
                int ny = j + direct[k][1];
 
                if (visit[nx][ny]) {
                    list[i][j] = 0;
                    ans--;
                    break;
                }
            }
        }
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
            if (list[i][j]) pre++;
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    if (!pre) cout << "0\n0\n";
    for (int T = 1; pre ; T++) {
        bfs();
        func();
        if (!ans) {
            cout << T << '\n' << pre << '\n';
            break;
        }
 
        pre = ans;
    }
 
    return 0;
}
 cs

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[101][101];
    static boolean visit[][] = new boolean[101][101];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, cnt;
 
    static void removeCheese() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (list[i][j] == 1) {
                    boolean chk = false;
                    for (int d = 0; d < 4; d++) {
                        int nx = i + direct[d][0];
                        int ny = j + direct[d][1];
 
                        if (visit[nx][ny]) {
                            chk = true;
                            break;
                        }
                    }
 
                    if (chk) {
                        list[i][j] = 0;
                        cnt--;
                    }
                }
            }
        }
    }
 
    static void bfs() {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { 0, 0 });
        visit[0][0] = true;
 
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
 
            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] == 1)
                    continue;
 
                dq.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
    }
 
    static void init() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(visit[i], false);
        }
    }
 
    static void func() {
        int pre = cnt;
        for (int t = 1;; t++) {
            bfs();
            removeCheese();
            init();
            if (cnt == 0) {
                System.out.println(t);
                System.out.println(pre);
                return;
            }
            pre = cnt;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == 1)
                    cnt++;
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 2638 치즈  (0) 2021.01.22
boj 17142 연구소 3  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22
boj 3055 탈출  (0) 2021.01.22
boj 2234 성곽  (0) 2021.01.22

+ Recent posts

티스토리툴바