1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
배추영역 하나에 지렁이 한마리가 들어가고 최종적으로 배추밭에 필요한 지렁이의 수를 구하는 문제이며
탐색을 통해 배추영역의 갯수를 구하는 문제입니다.
저는 bfs를 사용했습니다.
입력으로 배추의 위치가 X, Y로 주어지면 list[X][Y] = 1로 표시합니다.
모든 입력을 다 받고 2중 for문을 돌려서 해당 칸이 1이면서 아직 방문하지 않은 위치면 그 위치를 시작으로 bfs를 돌립니다.
bfs로 현재 위치에서 주변에 1이 있는 좌표들을 큐에 넣고 중복체크를 해줍니다.
bfs 탐색이 종료되면 한 구역 탐색이 끝난 것이므로 ans를 1 증가시켜 다 돌고나면 최종 답을 출력합니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static boolean visit[][];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int list[][];
static int N, M, K, ans;
static void print() {
sb.append(ans + "\n");
ans = 0;
}
static void bfs(int sx, int sy) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[] { sx, sy });
visit[sx][sy] = true;
while (!q.isEmpty()) {
int x = q.peek()[0];
int y = q.peek()[1];
q.remove();
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] == 0)
continue;
q.add(new int[] { nx, ny });
visit[nx][ny] = true;
}
}
}
static void func() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j] == 1) {
if (visit[i][j])
continue;
bfs(i, j);
ans++;
}
}
}
}
static void input() throws Exception {
int u, v;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
list = new int[N][M];
visit = new boolean[N][M];
while (K-- > 0) {
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
list[u][v] = 1;
}
}
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine());
int tc = Integer.parseInt(st.nextToken());
while (tc-- > 0) {
input();
func();
print();
}
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 20304 비밀번호 제작 (0) | 2021.02.08 |
|---|---|
| boj 2606 바이러스 (0) | 2021.02.03 |
| boj 16956 늑대와 양 (0) | 2021.02.03 |
| boj 20419 화살표 미로 (Easy) (0) | 2021.01.23 |
| boj 2638 치즈 (0) | 2021.01.22 |