https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
import java.io.*;
import java.util.StringTokenizer;
public class Main {
final static int MAX = 50 + 10; // 최대 50 + 여분 (10)
static boolean map[][];
static boolean visited [][];
static int T, N, M, K;
// y, x를 기준으로 (-1, 0) 이면 위, (1, 0) 이면 아래, (0, -1) 이면 왼쪽, (0, 1) 이면 오른쪽
static int [] dirY = {-1, 1, 0 ,0};
static int [] dirX = {0, 0, -1 ,1};
static void dfs(int y, int x) { // 좌표와 배열의 차이로 x,y 반대로 들어감
visited[y][x] = true;
for (int i = 0; i < 4; i++) {
int newY = y + dirY[i]; // 다음 방문 지점
int newX = x + dirX[i];
// 새 방문 지점에 배추가 존재하며, 방문한 적 없음
if (map[newY][newX] && visited[newY][newX] == false){
dfs(newY, newX);
}
}
// dfs(y + 1, x); // 아래인 지점 방문
// dfs(y - 1, x); // 위
// dfs(y, x - 1); // 왼쪽
// dfs(y, x + 1); // 오른쪽
}
public static void main(String[] args) throws IOException {
// 0. 입력 및 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수
while (T-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken()); // 가로
N = Integer.parseInt(st.nextToken()); // 세로
K = Integer.parseInt(st.nextToken()); // 배추가 심어져 있는 위치의 개수
map = new boolean[MAX][MAX];
visited = new boolean[MAX][MAX];
// 1. map 정보 반영
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[y + 1][x + 1] = true;
}
// 2. dfs
int answer = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
// map[i][j] 지점에 배추가 존재하는지, 방문하지 않았는지
if (map[i][j] && visited[i][j] == false) {
answer++; // 지렁이 1마리 소비
dfs(i, j);
}
}
}
// 3. 출력
bw.write(String.valueOf(answer));
bw.newLine();
}
bw.close();
br.close();
}
}
'백준' 카테고리의 다른 글
BOJ[JAVA] 6603 로또 (0) | 2023.09.10 |
---|---|
BOJ[JAVA] 1946번 신입 사원 (1) | 2023.08.27 |
BOJ[JAVA] 2615 오목 (0) | 2023.08.21 |
BOJ[JAVA] 4949 균형잡힌 세상 (0) | 2023.07.31 |
BOJ[JAVA] 2607 비슷한 단어 (0) | 2023.07.31 |