728x90
반응형
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class 백준1012유기농배추 {
static int[][] baecho;
static int M;
static int N;
static int K;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static boolean[][] visit;
static int count;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
count=0;
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
baecho = new int[M][N];
visit = new boolean[M][N];
for (int j = 0; j < K; j++) {
StringTokenizer tt = new StringTokenizer(br.readLine());
int a = Integer.parseInt(tt.nextToken());
int b = Integer.parseInt(tt.nextToken());
baecho[a][b] = 1;
}
for (int x = 0; x < M; x++) {
for (int y = 0; y < N; y++) {
if (baecho[x][y] == 1 && !visit[x][y]) {
dfs_baechu(x,y);
count++;
}
}
}
System.out.println(count);
}
}
static void dfs_baechu(int x, int y){
visit[x][y] = true;
for (int i=0; i<4; i++) {
int xx = dx[i]+x;
int yy = dy[i]+y;
if (xx>=0 && yy>=0 && xx <M && yy<N && !visit[xx][yy] && baecho[xx][yy] ==1) {
dfs_baechu(xx,yy);
}
}
}
}
320x100
반응형
'ALGORITHM' 카테고리의 다른 글
[python3] 2023 KAKAO BLIND RECRUITMENT 개인정보 수집 유효기간 (0) | 2023.05.08 |
---|---|
[python 3] 2019 KAKAO BLIND RECRUITMENT 실패율 (0) | 2023.05.07 |
[피보나치 수열] 재귀호출, 배열 (1) | 2022.11.19 |
[이진 탐색] Binary Search Algorithm (0) | 2022.11.18 |
[ALGORITHM] Dynamic programming / 동적 계획법 (0) | 2022.10.13 |