알고리즘94 :: BOJ_1012_유기농배추
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
|
package backjun;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class backjun_1012_유기농배추 {
static int[][] map;
static int[] dx= {-1,1,0,0};
static int[] dy= {0,0,-1,1};
static int[][] check;
static int M;
static int N;
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int total = Integer.parseInt(br.readLine());
while(total-->0) {
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
//가로, 세로, 위치 개수
map = new int[M][N];
check = new int[M][N];
for(int i=0; i<K; i++)
{
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
map[x][y] = 1;
}
int ans = 0;
for(int i=0; i<M; i++) {
for(int j=0; j<N; j++) {
if(map[i][j] == 1 && check[i][j] ==0) {
check[i][j] = 1;
ans +=1;
dfs(i,j);
}
}
}
System.out.println(ans);
}
}
static void dfs(int x, int y) {
for(int i=0; i<4; i++) {
int ddx = x + dx[i];
int ddy = y + dy[i];
if(ddx<0 || ddx>=M || ddy<0 || ddy>=N) {
continue;
}
if(map[ddx][ddy] ==1 && check[ddx][ddy] == 0) {
check[ddx][ddy] = 1;
dfs(ddx,ddy);
}
}
}
}
|
cs |
1을 묶음 단위로 DFS 구현하면 해결할 수 있습니다.
기본적으로 완전탐색 문제에 해당됩니다.
'알고리즘' 카테고리의 다른 글
알고리즘96 :: 거북이 문방구집 (0) | 2020.08.29 |
---|---|
알고리즘95 :: 다익스트라 로직 (0) | 2020.08.23 |
알고리즘93 :: 릿코드 시작 (0) | 2020.08.19 |
알고리즘 92 :: BOJ_내리막길(DFS, DP) [진행중] (0) | 2020.08.12 |
알고리즘91 :: 응용 알고리즘(선택정렬, 버블정렬, 삽입정렬) (0) | 2020.08.09 |
댓글
이 글 공유하기
다른 글
-
알고리즘96 :: 거북이 문방구집
알고리즘96 :: 거북이 문방구집
2020.08.29 -
알고리즘95 :: 다익스트라 로직
알고리즘95 :: 다익스트라 로직
2020.08.23 -
알고리즘93 :: 릿코드 시작
알고리즘93 :: 릿코드 시작
2020.08.19 -
알고리즘 92 :: BOJ_내리막길(DFS, DP) [진행중]
알고리즘 92 :: BOJ_내리막길(DFS, DP) [진행중]
2020.08.12