8월 8일 99클럽 항해 18일

99클럽 항해 18일차

 

오늘의 문제는 단지번호붙이기이다.

 

문제에서 주어진 지도를 보면 상하좌우로 인접한 셀을 탐색하며 깊이 우선 탐색 방식을 사용한다. 각 방향으로 이동하면서 현재 셀은 방문한 흔적을 남기기 위해서 0으로 변경한다. 인접한 셀에 1이 있다면, 재귀호출을 실행하고 count에 1을 더한다. 연결된 단지내의 집 수를 배열에 저장하고 arr을 정렬한 후 출력한다.

순으로 문제를 해결하였다.

 

 

 

import java.io.*;
import java.util.*;

public class Main{
    static int N, count;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    public static void dfs(int x, int y){
        map[x][y] = 0;
        count += 1;
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx>=0 && nx<N && ny>=0 && ny<N && map[nx][ny]==1) dfs(nx, ny);
        }
    }
    
    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 str = br.readLine();
            for(int j=0; j<N; j++){
                map[i][j] = str.charAt(j) - '0';
            }
        }
        
        ArrayList<Integer> arr = new ArrayList<>();
        int result = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                count = 0;
                if(map[i][j] == 1){
                    dfs(i,j);
                    arr.add(count);
                    result++;
                }
            }
        }
        
        Collections.sort(arr);
        System.out.println(result);
        for(int i : arr){
            System.out.println(i);
        }
    }
}