단지번호붙이기

조소복·2022년 9월 21일

문제

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

입력

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

출력

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

예제 입력 1

예제 출력 1

문제 풀이

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

public class Main {
    static int cnt;
    static int tmp;
    static int[][] moves={{1,0},{-1,0},{0,1},{0,-1}};
    static char[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

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

        map=new char[N][N];
        ArrayList<Integer> arr=new ArrayList<>();

        for(int i=0;i<N;i++){
            map[i]=br.readLine().toCharArray();
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(map[i][j]=='1'){
                    //dfs
                    map[i][j]='0';
                    dfs(N,i,j);
                    cnt++;
                    arr.add(tmp);
                    tmp=0;
                }
            }
        }

        System.out.println(cnt);
        arr.sort(((o1, o2) -> o1-o2));
        for(int i=0;i<arr.size();i++){
            System.out.println(arr.get(i)+1);
        }
    }

    private static void dfs(int N,int i,int j) {
        for(int[] m:moves){
            if(i+m[0]<0 || i+m[0]>=N || j+m[1]<0 || j+m[1]>=N) continue;
            if(map[i+m[0]][j+m[1]]=='1'){
                map[i+m[0]][j+m[1]]='0';
                tmp++;
                dfs(N,i+m[0],j+m[1]);
            }
        }
    }
}

주어진 값에서 상하좌우로 이어진 부분들을 모두 방문하고 몇 개의 그룹이 나오는지, 각 그룹 내에 몇 칸이 포함되어있는지 출력하면 되는 문제로 DFS를 이용하여 풀었다.

DFS 탐색

private static void dfs(int N,int i,int j) {
    for(int[] m:moves){
        if(i+m[0]<0 || i+m[0]>=N || j+m[1]<0 || j+m[1]>=N) continue;
        if(map[i+m[0]][j+m[1]]=='1'){
            map[i+m[0]][j+m[1]]='0';
            tmp++;
            dfs(N,i+m[0],j+m[1]);
        }
    }
}

집이 있는 곳의 위치값을 매개변수로 받고 상하좌우로 탐색하여 집이 있는 곳이 있다면 그곳으로 이동하여 또 한번 상하좌우 살펴보면서 집이 있는곳들을 탐색한다.

이렇게 하면 상하좌우로 이어져있는 집들을 모두 방문할 수 있게 되는데 방문했다는 표시를 그래프에 0으로 표시함으로써 방문했다고 체크해준다.

그리고 이때, 각 그룹내의 집이 몇 개 있는지도 출력해야하기 때문에 집에 방문할때마다 tmp에 값을 추가해주고 한 그룹의 모든 탐색이 끝났을 때 ArrayList에 값을 추가해준 뒤 tmp=0으로 초기화해준다.

답 출력하기

for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
        if(map[i][j]=='1'){
            //dfs
            map[i][j]='0';
            dfs(N,i,j);
            cnt++;
            arr.add(tmp);
            tmp=0;
        }
    }
}

System.out.println(cnt);
arr.sort(((o1, o2) -> o1-o2));
for(int i=0;i<arr.size();i++){
    System.out.println(arr.get(i)+1);
}