1012 유기농 배추
2020. 2. 4. 13:46ㆍLearn/Algorithm
|
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
|
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
static int test;
static int cnt;
static int Nor;
static int Mor;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
test = sc.nextInt();
for(int t = 0; t < test; t++) {
Nor = sc.nextInt();
Mor = sc.nextInt();
int Man = sc.nextInt();
int arr[][] = new int [Nor][Mor];
boolean arr2[][] = new boolean [Nor][Mor];
ArrayList<Integer> al = new ArrayList<>();
int a= 0;
int b = 0;
for(int i = 0; i < Man; i++) {
a = sc.nextInt();
b = sc.nextInt();
arr[a][b] = 1;
}
for(int i = 0; i < Nor; i++) {
for(int j = 0; j < Mor; j++) {
if(arr[i][j] == 1) {
cnt = 0;
DFS(i,j,cnt,arr,arr2);
if(cnt != 0)
al.add(cnt);
}
}
}
System.out.println(al.size());
}
}
public static void DFS(int n,int w,int c,int ar[][],boolean ar2[][]) {
if(ar2[n][w] == false)
cnt++;
ar2[n][w] = true;
for(int i = 0; i < 4; i++) {
int nn = n + dx[i];
int ww = w + dy[i];
if(nn >= 0 && nn < Nor && ww >= 0 && ww < Mor ) {
if(ar2[nn][ww] == true)
continue;
if(ar[nn][ww] == 1) {
DFS(nn,ww,cnt,ar,ar2);
}
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
|
단지번호 붙이기 문제를 풀었다면 그냥 갖다붙여도 맞는 문제.
DFS와 사방탐색을 통해 따로 떨어져 있는 그룹들을 찾는 문제.
'Learn > Algorithm' 카테고리의 다른 글
| 7576 토마토 (0) | 2020.02.04 |
|---|---|
| 2178번 미로 탐색 (0) | 2020.02.04 |
| 2667 단지번호붙이기 (0) | 2020.02.04 |
| 1260 DFS 와 BFS - 백준 (0) | 2020.02.04 |
| 14720 우유축제 (0) | 2020.02.03 |