[백준] 11123 양 한마리.. 양 두마리..

문제 출처: https://www.acmicpc.net/problem/11123

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

 

1. 입력

: 첫 번째 줄은 테스트 케이스의 수를 나타나는 T를 입력받는다.

: 이후 각 테스트 케이스의 첫 번째 줄에서는 H,W 를 입력받는다. H는 그리드의 높이이고, W는 그리드의 너비이다. 이후 : 그리드의 높이 H 에 걸쳐서 W개의 문자로 이루어진 문자열 하나를 입력받는다. 

• 0 < T ≤ 100
• 0 < H, W ≤ 100

 

 

2. 결과

: 각 테스트 케이스마다, 양의 몇 개의 무리로 이루어져 있었는지를 한 줄에 출력하면 된다. 

 

 

3. 풀이

: 양의 정보를 배열에 입력받는다.

: 양을 만나게 되면 상하좌우를 살피며 양이 아닌 상태인 "."로 바꿔주며 방문표시와 한 울타리에 있는 양을 중복해서 카운트하지 않도록 한다.

: 새로운 울타리에서 양을 만날 때만 카운트 하여 몇 개의 울타리로 구성되어 있는지를 구한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 양한마리 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int R, C;
	static char[][] map;
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	public static void main(String[] args) throws Exception{
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			
			map = new char[R][C];
			for(int i = 0; i < R; i++) {
				String str = br.readLine();
				for(int j = 0; j < C; j++) {
					map[i][j] = str.charAt(j);
				}
			}
			
			int cnt = 0;
			
			for(int i = 0; i < R; i++) {
				
				for(int j = 0; j < C; j++) {
					if(map[i][j] == '#') {
						cnt++;
						bfs(i, j);
					}
				}
			}
			
			sb.append(cnt + "\n");
			
		}
		System.out.println(sb);
	}
	static class Point{
		int r, c;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		
	}
	private static void bfs(int r, int c) {
		Queue<Point> q = new LinkedList<>();
		q.offer(new Point(r, c));
		map[r][c] = '.';
		
		while(!q.isEmpty()) {
			Point cur = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				
				if(nr < 0 || nr >= R || nc < 0 || nc >=C || map[nr][nc] == '.')continue;
				q.offer(new Point(nr, nc));
				map[nr][nc] = '.';
			}
		}
		
	}
}