백준 1012. 유기농 배추
16 Aug 2021문제 바로가기
문제 요약
배추를 유기농으로 키우려고 배추흰지렁이를 구입해서 키울 예정인데 상하좌우 중 한군데라도 이어져 있으면 지렁이가 이동해서 해충을 없앨 수 있다고 한다. 전체 배추가 재배되는 땅의 정보가 주어질 때 최소 몇 마리의 지렁이가 필요한지 알아보자.
문제 풀이 포인트
크게 어려울 것 없는 탐색 문제이다. 깊이 우선, 혹은 넓이 우선으로 풀 수 있으며 섬의 개수를 찾는 문제문제와 비슷한 문제 방식이다.
연결되어 있는 배추를 모두 체크하면서 탐색하면 되는 탐색의 기본적인 문제라고 할 수 있다. 한가지 신경써야할 부분은 가로(M)와 세로(N)와 배추의 좌표가 굉장히 헷갈리게 주어질 수 있으니 신경써야한다.
문제 코드[JAVA]
코드 펼치기
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int[][] check;
static int N, M;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
M = sc.nextInt(); // 가로
N = sc.nextInt(); // 세로
int K = sc.nextInt();
boolean[][] arr = new boolean[N][M];
check = new int[N][M];
for (int i = 0; i < K; i++) {
int x = sc.nextInt(); // 가로
int y = sc.nextInt(); // 세로
arr[y][x] = true;
}
int color = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(check[i][j] != 0) continue;
if(arr[i][j]) {
sol(i, j, arr, color);
color++;
}
}
}
System.out.println(color-1);
}
}
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
private static void sol(int i, int j, boolean[][] arr, int color) {
Queue<int[]> queue = new LinkedList<>();
boolean[][] v = new boolean[N][M];
queue.add(new int[]{i, j});
v[i][j] = true;
while(!queue.isEmpty()) {
int[] cur = queue.poll();
check[cur[0]][cur[1]] = color;
for(int d = 0; d < 4; d++){
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if(nx < 0 || nx >= N || ny < 0 || ny >= M || v[nx][ny]) continue;
if(arr[nx][ny]) {
queue.add(new int[] {nx, ny});
v[nx][ny] = true;
}
}
}
}
}