[백준 1012] 유기농 배추

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

---

메인 메소드

static int[] nX = {-1, 0, 1, 0};	//DFS때 사용하기 위한 (다음 배열 위치) nX, nY 배열
static int[] nY = {0, -1, 0, 1};
static int[][] checker; // 방문했는지 아닌지 체킹용 배열

public static void main(String[] args) throws IOException{
	Q1012 t = new Q1012();
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int loopCnt = Integer.parseInt(st.nextToken());	// 테스트케이스
	int width;
	int height;
	int baechu;	//배추 수
	int[][] arr;
	
	for(int k=0; k<loopCnt; k++) {
		st = new StringTokenizer(br.readLine());
		width = Integer.parseInt(st.nextToken());
		height = Integer.parseInt(st.nextToken());
		baechu = Integer.parseInt(st.nextToken());
		
		//배열의 길이 값들을 받아 생성 배추밭이랑 체킹배열
		arr = new int[height][width];
		checker = new int[height][width];
		int x;
		int y;
		
		//배추 표시
		for(int i=0; i<baechu; i++	) {
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			arr[y][x] = 1;
		}
		
		//배추밭을 돌면서 연달아 붙은 배추가 보이면 거기 좌표부터 DFS
		int answer = 0;
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr[0].length; j++) {
				//배추가 있고 방문하지 않은 배추자리라면 체크표시 하고 DFS 쭉 돌고 answer 1 출력 
				if(arr[i][j]==1 && checker[i][j]==0) {
					checker[i][j]=1;
					t.baechuDFS(arr, i, j);
					answer++;
				}
			}
		}
		System.out.println(answer);
	}
}

일단 메인 메소드 전에 연달아 붙어있는 배추를 확인하기 위한 static int배열 변수 nX, nY 를 만들어주었고,
나중에 DFS를 할때 방문여부 확인을 위한 checker 배열을 만들어놨습니당.
그리고 입력 형식에 맞춰 변수들을 선언했구요... (개인적으로 2차배열 사용할 때 가로 세로 순서형식으로 주는거 싫어함... 뜬금없이 헷갈려짐)
입력받은 길이와 높이에 맞춰 배추밭 배열과 체크용 배열을 생성해줍니다.
이후 배추들의 자리를 표시해주고,
이제 배추밭을 첨부터 쭉 ㄱㄱ 하면서 배추가 발견되면 첨 보는 배추인지 체크합니다
그 자리 배추를 방문했다고 표시하고 연달아 붙은 배추를 찾으러 DFS 하러 갑시다.
(한번 DFS를 쭉 돌고 answer 를 1 올려주어야 함.)

---

baechuDFS 메소드

public void baechuDFS(int[][] arr, int x, int y) {
	int nextX = 0;
	int nextY = 0;
	// 현재 배추자리의 상하좌우를 돌며 다음 자리를 셋팅하며 진행 
	for(int i=0; i<4; i++) {
		nextX = x + nX[i];
		nextY = y + nY[i];
		//다음자리가 배열밖으로 넘어간다면 continue
		if(nextX<0 || nextY<0 || nextX>=arr.length || nextY>=arr[0].length) {
			continue;
		}
		// 다음 자리에 배추가 있고 방문하지 않았었던 자리라면  
		// 체킹용 배열에 방문체크 후 그 자리로 다시 DFS 재귀호출.
		if(arr[nextX][nextY]==1 && checker[nextX][nextY]==0) {
			checker[nextX][nextY] = 1;
			baechuDFS(arr, nextX, nextY);
		}
	}
}

배추 상하좌우를 검사하기 위한 다음 좌표 변수를 선언하고
맨 위에 만들어 놓았던 nX, nY를 사용해 다음 자리를 계산해용
다음 자리가 배추밭 배열의 범위를 벗어가는 경우 continue, 옆자리에 배추가 있고 첨보는 배추라면 그 좌표를 들고 다시 baechuDFS를 재귀호출합니다

---

이상하거나 잘못된 부분이 있다면 알려주세용

오랜만에 DFS를 쓴거같은데 BFS로 해도 상관 없어보입니당