유기농 배추(1012)
풀이
- 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
}
class Pos {
public int x;
public int y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
}
public class Main {
static int arr[][];
static boolean visited[][];
static int checkX[] = {0, 0, -1, 1}; // 상, 하, 좌, 우
static int checkY[] = {-1, 1, 0, 0};
static int M;
static int N;
static int K;
public static void main(String args[]) throws IOException {
FastScanner sc = new FastScanner();
int T = sc.nextInt(); // Test Case
for (int j = 0; j < T; j++) {
Queue<Pos> cabbage = new LinkedList<>();
int cnt = 0;
M = sc.nextInt(); // 세로 길이
N = sc.nextInt(); // 가로 길이
K = sc.nextInt(); // 배추가 심어져 있는 수
arr = new int[M][N];
visited = new boolean[M][N];
for (int i = 0; i < K; i++) {
int a = sc.nextInt(); // 세로
int b = sc.nextInt(); // 가로
cabbage.add(new Pos(b, a)); // 배추가 심어져 있는 위치
arr[a][b] = 1;
}
while (!cabbage.isEmpty()) {
Pos tmp = cabbage.poll();
int x = tmp.getX();
int y = tmp.getY();
if(arr[y][x] == 1 && !visited[y][x]) {
bfs(x, y);
cnt++;
}
}
System.out.println(cnt);
}
}
public static void bfs(int x, int y) {
Queue<Pos> queue = new LinkedList<>();
queue.add(new Pos(x, y));
while (!queue.isEmpty()) {
Pos Cur = queue.poll();
int curX = Cur.getX();
int curY = Cur.getY();
visited[y][x] = true;
for (int i = 0; i < 4; i++) {
int dx = curX + checkX[i];
int dy = curY + checkY[i];
if (dx >= 0 && dx < N && dy >= 0 && dy < M) { // 범위를 벗어나지 않고
if (arr[dy][dx] == 1 && !visited[dy][dx]) {
queue.add(new Pos(dx, dy));
visited[dy][dx] = true;
}
}
}
}
}
}