[백준] 11213 양 한마리... 양 두마리... - BFS(너비우선탐색) + DFS(깊이우선탐색) JAVA

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

코드설명

BFS(너비우선탐색) + DFS(깊이우선탐색) 를 활용합니다.

 

DFS로 섬 무리의 개수를 세주고, 이후에는 더 이상 세지 않도록 합니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static char[][] matrix;
	static int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			H = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			
			matrix = new char[H][W];
			for(int i=0; i<H; i++) {
				st = new StringTokenizer(br.readLine());
				matrix[i] = st.nextToken().toCharArray();
			}
			
			answer = 0;
			for(int i=0;i<H; i++) {
				for(int j=0;j<W; j++) {
					if(matrix[i][j] == '#') {
						answer += DFS(i, j);
					}
				}
			}
			System.out.println(answer);
		}
		
		
	}
	static int DFS(int r, int c) {
		
		for(int dir = 0; dir < 4; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			
			if(nr < 0 || nr >=H || nc < 0 || nc >= W) continue;
			if(matrix[nr][nc] == '.')  continue;
			matrix[nr][nc] = '.';
			DFS(nr, nc);
		}
		return 1;
	}
}