백준 11123번 : 양 한마리... 양 두 마리...

 문제

www.acmicpc.net/problem/11123

11123번: 양 한마리... 양 두마리...

11123 양 한마리... 양 두마리...

 

 구현 방법

 dfs로 구현하였습니다. 값이 '#'일 때만 탐색하고 탐색할 때마다 방문의 표시로 '.' (빈 칸)으로 바꿔주고 카운트를 세어줍니다.

 

 구현 코드

package BOJ.Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ11123_양한마리양두마리 {
	static int R, C, cnt;
	static int[][] deltas= {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static char[][] map;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int tc=0;tc<TC;tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			map = new char[R][C];
			for (int r=0;r<R;r++) {
				String input = br.readLine();
				map[r] = input.toCharArray();
			}
			cnt = 0; // cnt 초기화
			// 입력완료
			for (int r=0;r<R;r++) {
				for (int c=0;c<C;c++) {
					if (map[r][c]=='#') {
						cnt++; // 탐색할때마다 카운트 세주기
						dfs(r, c);
					}
				}
			}
			sb.append(cnt+"\n");
		}
		System.out.println(sb);
	}
	
	static void dfs(int r, int c) {
		map[r][c] = '.';
		for (int d=0;d<4;d++) {
			int nr = r+deltas[d][0];
			int nc = c+deltas[d][1];
			if (isIn(nr,nc) && map[nr][nc]=='#') {
				dfs(nr, nc);
			}
		}
		return;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!