[Baekjoon] 2667번 단지번호붙이기(feat. Java)

접근

• 단지에 대한 접근은 DFS 로 처리
• 단지구분은 숫자로 하여 DFS 가 접근한 단지에 대해 숫자로 기록
• DFS 가 끝나면 단지 탐색이 끝나게 된 것임으로 단지 숫자 증가

 

---

 

해결

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

public class Main {

    static int N;
    static int[][] arr;
    static int[][] visited;
    static int beaconValue = 1; // 단지 번호

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

        arr = new int[N+1][N+1];
        visited = new int[N+1][N+1];

        for(int i=1;i<=N;i++){
            String[] arr1 = br.readLine().split("");

            for(int j=1;j<=N;j++){
                arr[i][j] = Integer.parseInt(arr1[j-1]);
            }
        }

        for(int y=1;y<=N;y++){
            for(int x=1;x<=N;x++){
                if(arr[y][x] == 1 && visited[y][x] == 0) {
                    dfs(y, x);
                    beaconValue += 1; // 단지 번호 증가
                }
            }
        }

        // 단지 수
        int danziCount = beaconValue - 1;

        int[] result = new int[danziCount];

        for(int y=1;y<=N;y++){
            for(int x=1;x<=N;x++){
                int danziValue = visited[y][x];

                if(0 < danziValue)
                    result[danziValue-1] += 1; // 단지별 집 수
            }
        }

        Arrays.sort(result);

        System.out.println(danziCount);

        for (int j : result) {
            System.out.println(j);
        }
    }

    public static void dfs(int Y, int X){
        if(arr[Y][X] == 0)
            return;

        visited[Y][X] = beaconValue;

        if(0 < X - 1 && arr[Y][X-1] == 1 && visited[Y][X-1] == 0){
            dfs(Y, X-1);
        }

        if(X + 1 <= N && arr[Y][X+1] == 1 && visited[Y][X+1] == 0){
            dfs(Y, X+1);
        }

        if(0 < Y - 1 && arr[Y-1][X] == 1 &&visited[Y-1][X] == 0){
            dfs(Y-1, X);
        }

        if(Y + 1 <= N && arr[Y+1][X] == 1 &&visited[Y+1][X] == 0){
            dfs(Y+1, X);
        }
    }
}