[백준] 1012번 유기농 배추

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

목표 : 2차원 배열에서 배추가 심어져 있는 땅에 지렁이가 총 몇마리 필요한지 구하기 1은 배추가 심어져있는 땅이고 인접한 배추들은 1마리의 지렁이만 필요하다.  DFS 활용  count 변수를 활용해 지렁이 개수를 세줌  주의할 부분은 방문처리와 count 변수를 초기화 해주는 것

import java.util.Arrays;
import java.util.Scanner;

//유기농 배추
public class Main {
	static int T, M, N, K, count = 0;
	static int[][] map, dir = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
	static boolean[][] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			K = sc.nextInt();

			map = new int[N][M];
			visited = new boolean[N][M];

			for (int k = 0; k < K; k++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				map[x][y] = 1;
			} // end of input

//			for (int i = 0; i < N; i++) {
//				System.out.println(Arrays.toString(map[i]));
//			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] == 1 && !visited[i][j]) {

						dfs(i, j);
						count++;
					}

				}
			}
		
			System.out.println(count);
			visited = new boolean[N][M];
			count=0;
			
		} // end of tc
	}// end of main

	public static void dfs(int x, int y) {
		visited[x][y] = true;
		for (int k = 0; k < 4; k++) {
			int nx = x + dir[k][0];
			int ny = y + dir[k][1];
			if (isInside(nx, ny) && map[nx][ny] == 1 && !visited[nx][ny]) {

				dfs(nx, ny);
			}
		}
	}

	public static boolean isInside(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < M;
	}

}