[문제] 단지번호 붙이기 2667번

문제

소스코드

import java.util.Arrays;
import java.util.Scanner;

public class Dangi {
	public static final int[] dx = {0,0,1,-1};
	public static final int[] dy = {1,-1,0,0};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		int[][] a = new int[n][n];
		for(int i=0; i<n; i++){
			String s = sc.nextLine();
			for(int j=0; j<n; j++){
				a[i][j] = s.charAt(j) - '0';
			}
		}
		int cnt = 0;
		int[][] group = new int[n][n];
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(a[i][j] == 1 && group[i][j] ==0){
					dfs(a, group, i, j, ++cnt, n);
				}
			}
		}	
		int[] ans = new int[cnt];
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(group[i][j] != 0){
					ans[group[i][j]-1] = ans[group[i][j]-1]+1;
				}
			}
		}
		Arrays.sort(ans);
		System.out.println(cnt);
		for(int i=0; i<cnt; i++){
			System.out.println(ans[i]);
		}
	}

	private static void dfs(int[][] a, int[][] group, int x, int y, int cnt, int n) {
		group[x][y] = cnt;
		for(int k=0; k<4; k++){
			int nx = x+dx[k];
			int ny = y+dy[k];
			if(0<= nx && nx < n && 0<=ny && ny<n){
				if(a[nx][ny] == 1 & group[nx][ny] == 0)
				dfs(a, group, nx, ny, cnt, n);
			}
		}	
	}
}

풀이

크게 3가지 부분으로 나눌 수 있다.

첫 번째, a[]는 그림 1의 단지를 담는 배열을 선언한다. 입력 값을 받아 반복문으로 배열을 담는다. 

두 번째, 단지별 호수인 cnt 값을 0으로 선언한다. 그림 2의 단지인 group[] 배열을 선언한다. a 배열에 1인 값(집이 있는 곳)과 group 배열에 0인(집이 없는 곳)을 찾는다. 깊이 우선 탐색(DFS) 방법을 사용하여 dfs 메소드를 통해 단지의 위, 아래, 오른쪽, 왼쪽을 탐색한다. 재귀호출을 통해 이어진 곳을 탐색하여 group[] 배열에 cnt(단지 호수)를 할당한다.

세 번째, 최종 결과를 담을 배열 ans[]를 선언한다. 단지 호수로 ans 배열에 index 값을 할당하여 반복문을 통해 담는다. 그 후 오름차순으로 정렬한다. 마지막으로 출력을 한다 !