algorithm/bfs
boj 2573 빙산
와이에쓰
2021. 4. 5. 22:18
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
먼저 빙산 주위에 바다가 있는 위치 수만큼 빙산이 녹습니다.
이중for문으로 이거를 확인해주시면 되고, 주위에 바다가 있을 때마다 cnt[i][j]를 1씩 늘려줍니다.
그 다음 이중for문을 다시 돌려서 cnt[i][j]만큼 빙산을 녹여줍니다.
빙산을 녹이는 과정에서 빙산이 두 덩어리 이상으로 분리가 되면 그 시간을 출력해주시면 됩니다.
이 과정을 bfs로 구현하였습니다. 이중for문을 돌면서 방문안된 빙산을 발견하면 bfs를 호출하는데
만약 두 번째로 bfs에 들어가게 되면 빙산이 분리가 되었다는 말이 되기때문에 바로 시간을 출력해주시면 됩니다.
저는 문제를 읽어보니 최초로 주어지는 입력에는 무조건 빙산이 한 덩어리라는 조건이 없어서
빙산이 두 덩어리 이상으로 분리가 되었는지 체크하는 bfs함수를 먼저 호출하였습니다.
|
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
|
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[300][300];
static int cnt[][] = new int[300][300];
static boolean visit[][] = new boolean[300][300];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int N, M;
static void init() {
for (int i = 0; i < N; i++)
Arrays.fill(visit[i], false);
}
static void bfs(int sx, int sy) {
Deque<int[]> dq = new ArrayDeque<>();
dq.add(new int[] { sx, sy });
visit[sx][sy] = 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 (visit[nx][ny] || list[nx][ny] == 0)
continue;
dq.add(new int[] { nx, ny });
visit[nx][ny] = true;
}
}
}
static void func() {
for (int t = 0;; t++) {
boolean chk = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j] == 0 || visit[i][j])
continue;
if (chk) {
System.out.println(t);
return;
}
bfs(i, j);
chk = true;
}
}
if (!chk) {
System.out.println(0);
return;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j] == 0)
continue;
for (int k = 0; k < 4; k++) {
int nx = i + direct[k][0];
int ny = j + direct[k][1];
if (list[nx][ny] == 0)
cnt[i][j]++;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j] == 0)
continue;
list[i][j] = list[i][j] >= cnt[i][j] ? list[i][j] - cnt[i][j] : 0;
cnt[i][j] = 0;
}
}
init();
}
}
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());
}
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |