Backjoon 11123 양 한마리... 양 두마리... JAVA

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

문제

얼마 전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지.  그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!"  정말 도움이 안 되는 친구라고 생각했었지. 그런데 막상 또다시 잠을 청해보려고 침대에 눕고 보니 양을 세고 있더군... 그런데 양을 세다 보니 이걸로 프로그램을 하나 짜볼 수 있겠단 생각이 들더군 후후후... 그렇게 나는 침대에서 일어나 컴퓨터 앞으로 향했지.

양을 # 으로 나타내고 . 으로 풀을 표현하는 거야. 서로 다른 # 두 개 이상이 붙어있다면 한 무리의 양들이 있는거지. 그래... 좋았어..! 이걸로 초원에서 풀을 뜯고 있는 양들을 그리드로 표현해 보는거야!

그렇게 나는 양들을 그리드로 표현하고 나니까 갑자기 졸렵기 시작했어. 하지만 난 너무 궁금했지. 내가 표현한 그 그리드 위에 몇 개의 양무리가 있었는지! 그래서 나는 동이 트기 전까지 이 프로그램을 작성하고 장렬히 전사했지. 다음날 내가 잠에서 깨어났을 때 내 모니터에는 몇 개의 양무리가 있었는지 출력되어 있었지.

조건

[입력]

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

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

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

[출력]

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

풀이

해당 문제는 전형적인 dfs 문제였다. 2차원 배열을 방문하면서 그룹의 개수를 출력하는 문제였고 방문 여부와 양인지 늑대인지에 따라 dfs를 돌도록 설정해주고 이후 배열을 범위를 벗어나거나 이미 방문했거나 양이 아닌 경우를 제외하고 모두 dfs를 돌려주고 처음 dfs를 들어갈 때 카운트를 증가시켜 최종 리턴해주면 문제를 해결할 수 있다.

코드

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

public class Main {

	static char[][] map;
	static int N, M, dy[] = {-1,1,0,0}, dx[] = {0,0,-1,1};
	static boolean[][] visit;
	public static void main(String[] args) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			int cnt = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new char[N][M];
			visit = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				map[i] = br.readLine().toCharArray();
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(!visit[i][j] && map[i][j] == '#') { // 방문 안했고 양인경우
						dfs(i,j);
						cnt++;
					}
				}
			}
			System.out.println(cnt);
		}
	}
	private static void dfs(int y, int x) {
		visit[y][x]= true;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny <0 || nx <0 || ny >= N || nx >= M || visit[ny][nx] || map[ny][nx] != '#') // 배열범위 벗어나거나 이미 방문했거나 양이 아닌경우
				continue;
			dfs(ny,nx);
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드