[백준 2667번] 단지번호붙이기

문제

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

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

---

정답

단지를 하나의 그래프라고 생각해보자. 문제에서 준 그림에는 3개의 단지가 있으니 그래프가 3개가 있다고 생각해보 무방하다.
각각의 그래프는 DFS든 BFS든 탐색을 하면 전체탐색을 하게 된다. 이 말은 각 그래프마다 1번의 탐색으로 그래프 전체를 알 수 있다는 것이다. 3개 단지이니까 총 3번을 탐색을 하게 된다.

그럼 결론은 배열을 돌면서 단지를 만나면 DFS는 BFS는 탐색을 하면서 들렸던 아파트를 체크한다. 탐색이 다 끝나면 다음 배열을 조회하면서 탐색하지 않은 아파트를 찾아서 탐색한다. 탐색한 횟수가 단지의 총 갯수이고 아파트의 갯수는 탐색을 할때 카운트해서 배열에 저장하면 된다.
이렇게 풀었는데 for문 중첩이 너무 많아져서 맘에 들지 않는다. 혹시 더 좋은 방법이 있다면 댓글로 알려주길 바란다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static class Graph{
        //목표좌표
        private int N,M;
        //미로를 구성할 배열
        private int[][] maze;
        //단지수를 저장할 배열
        ArrayList<Integer> apt;
        //생성자
        //미로 크기 생성
        public Graph(int n, int m) {
            this.maze = new int[n+2][m+2];
            this.N = n;
            this.M = m;
            apt = new ArrayList<Integer>();
        }
        //미로 구성 함수
        public void addMaze(int row, int[] m) {
            for(int i=0; i<m.length; i++) {
                maze[row][i+1] = m[i];
            }
        }
        //깊이우선 탐색
        public void DFS(int v, int w, int aptorder) {
            //일단 집 이 있으니 단지수 채워야함
            apt.add(0);

            //집이 있는 곳이니까 0으로 바꿈
            maze[v][w]=0;

            DFSUtil(v,w,aptorder);
        }

        public void DFSUtil(int v,int w, int aptorder) {
            //집이 있는 곳이니까 0으로 바꿈
            maze[v][w]=0;

            apt.set(aptorder, apt.get(aptorder)+1);

            //주변 노드들 확인
            if(maze[v-1][w] == 1) {
                DFSUtil(v-1,w,aptorder);
            }
            if(maze[v+1][w] == 1) {
                DFSUtil(v+1,w,aptorder);            
            }
            if(maze[v][w-1] == 1) {
                DFSUtil(v,w-1,aptorder);
            }
            if(maze[v][w+1] == 1) {
                DFSUtil(v,w+1,aptorder);
            }
        }

        class Node{
            int v;
            int w;
            public Node(int v, int w) {
                this.v= v;
                this.w = w;
            }
        }

    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuffer sf = new StringBuffer();

        int N = Integer.parseInt(br.readLine());

        Graph g = new Graph(N,N);

        //지도 생성 for 문
        for(int i=0 ;i<N ;i++) {
            String minfo = br.readLine();
            int [] mm = new int[N];
            for(int j=0 ;j<N ;j++) {
                mm[j] = Integer.parseInt(minfo.substring(j, j+1));
            }
            g.addMaze(i+1, mm);
        }

        //단지 확인
        int aptorder=0;//단지 갯수
        for(int i=1; i<N+2; i++) {
            for(int j=1; j<N+2 ; j++) {
                if(g.maze[i][j] == 1) {
                    g.DFS(i, j, aptorder);
                    aptorder++;
                }
            }
        }
        System.out.println(g.apt.size());
        Collections.sort(g.apt);
        for(int i=0;i<g.apt.size();i++) {
            System.out.println(g.apt.get(i));
        }

        br.close();
        bw.flush();
        bw.close();
    }
}