[BOJ] 2667번: 단지번호붙이기 (Java)

[Java] 2667 - 단지번호붙이기

 

[문제]

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

[풀이]

대표적인 DFS, BFS로 풀 수 있는 문제이다. DFS가 더 익숙해서 DFS로 풀었다.

주어진 2차원 배열을 DFS로 탐색하면서 1일 경우 단지수가 존재함(count)을 체크하면 된다.

 

0	1	1	0	1	0	0
0	1	1	0	1	0	1
1	1	1	0	1	0	1
0	0	0	0	1	1	1
0	1	0	0	0	0	0
0	1	1	1	1	1	0
0	1	1	1	0	0	0

좌표 [0, 0] 부터 상, 하, 좌, 우 순서로 탐색을 시작한다. 

좌표 [0, 0]은 0이므로 건너뛰고, 1인 [0, 1]에서 시작한다. (방문했으므로 visit 배열에 true 표시)

배열의 범위를 벗어나면 안되므로 배열이 0보다 크고, N보다 작을 경우 그리고 아직 방문하지 않았을 경우에만 DFS를 돌린다.

[0, 1] -> [1, 1] -> [2, 1] -> [2, 0] -> [2, 2] -> [1, 2] -> [0, 2] 순서로 재귀적으로 호출하며 깊게 타고 들어가면서 탐색을 진행한다.

 

count = 1이 끝났으면 count를 1 증가시켜서 [0, 4]부터 반복적으로 DFS를 다시 진행한다.

탐색이 끝나고 난 뒤에는 아래와 같이 단지수가 기록된다.

0	1	1	0	2	0	0
0	1	1	0	2	0	2
1	1	1	0	2	0	2
0	0	0	0	2	2	2
0	1	0	0	0	0	0
0	1	1	1	1	1	0
0	1	1	1	0	0	0

 

이와 같이 반복해준 후, 최종적인 단지의 갯수와 오름차순으로 정렬한 단지 내의 집의 수를 출력해주면 되는 문제이다.

 

[코드]

package algorithm.Baekjoon;

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

public class BOJ_2667 {
    static int map[][];
    static boolean visit[][]; // 방문 여부
    static int N; // 지도 최대 크기
    static int count = 1; // 총 단지 수
    static int x[] = {-1, 1, 0, 0}; // row
    static int y[] = {0, 0, -1, 1}; // col

    public static void dfs(int i, int j) {
        map[i][j] = count; // 방문한 집 표시
        visit[i][j] = true;

        // 상하좌우로 이동하며 탐색
        for(int k=0; k<x.length; k++) {
            int ix = i + x[k];
            int jy = j + y[k];

            // 배열의 범위를 벗어나지 않는 범위 내에서 탐색
            if(ix >= 0 && ix < N && jy >= 0 && jy < N) {
                if(map[ix][jy] == 1 && !visit[ix][jy]) { // 집이 있으면서 방문하지 않은 곳
                    dfs(ix, jy); // 연결 되어있는 단지 탐색
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        for(int i=0; i<N; i++) {
            String[] input = br.readLine().split("");
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
        /*
        for(int i=0; i<N; i++) {
            String input = scan.next();
            for(int j=0; j<N; j++) {
                map[i][j] = input.charAt(j)-'0';
            }
        }
        */

        visit = new boolean[N][N];
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j] == 1 && !visit[i][j]) { // 집이 있으면서 방문하지 않은 곳
                    dfs(i, j); // 연결 되어있는 단지 탐색
                    count++; // 다음 단지 수로 이동
                }
            }
        }

        // 총 단지 수
        System.out.println(count-1);
        // 단지 내 집의 수
        int result[] = new int[count];
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j] != 0)
                    result[map[i][j]]++;
            }
        }
        // 단지수를 오름차순으로 정렬하여 출력
        Arrays.sort(result);
        for(int i=1; i<result.length; i++) {
            System.out.println(result[i]);
        }
    }
}