백준-1012 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

---

DFS를 사용하여 풀이

arr[i][j]의 값이 1이고 방문X라면

배추흰지렁이수 +1 & DFS수행하여 인접배추밭에 방문체크함.

---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class 유기농배추 {
	static int M,N,K;
	static int [][]arr;//배추밭
	static boolean [][] visit;//방문배열
	static int bachunum;//배추흰지렁이의 수 
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/유기농배추.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			M=sc.nextInt();//가로길이
			N=sc.nextInt();//세로길이
			K=sc.nextInt();//배추가심어져있는 위치의 개수
			arr= new int[N][M];//인덱스 0부터시작
			visit = new boolean[N][M];//방문배열초기화
			bachunum=0;//배추흰지렁이의 수 초기화
			for (int i = 0; i < K; i++) {//K만큼 연산수행
				int n1=sc.nextInt();//열
				int n2=sc.nextInt();//행
				arr[n2][n1]=1;//행,열에 1입력
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(arr[i][j]==1 && !visit[i][j]) {//만약 1이고 방문x라면
						bachunum++;//배추흰지렁이 수 증가
						//여기서 dfs는 근처가 1인거의 방문체크를해주는역할
						dfs(i,j);
					}
				}
			}
			System.out.println(bachunum);//배추흰지렁이 갯수
			
		}
	}
	static int []dr = {-1,1,0,0};//상하좌우
	static int []dc = {0,0,-1,1};
	private static void dfs(int i, int j) {
		visit[i][j]=true;
		for (int k = 0; k <4; k++) {//사방탐색
			int nr = i+dr[k];
			int nc = j+dc[k];
			if(nr>=0 && nr<N && nc>=0 && nc<M && arr[nr][nc]==1 && !visit[nr][nc]) {//범위체크, 근처1, 방문X라면 
				dfs(nr,nc);
			}
		}
		
	}
	

}