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 |