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

내 풀이

모든 노드를 방문하여 조건에 맞는다면 탐색하는 알고리즘을 작성하여야 하기 때문에 DFS 사용

구현 아이디어는 다음과 같다.
1. 지도를 띄어쓰기 없이 입력받기 처리 (인접행렬)
2. 인접행렬을 모두 돌며 1일 때 DFS 수행
3. DFS 메소드 실행될 때마다 단지 수 +1
4. 단지 수 반환
5. 각 단지에 속하는 집의 수 오름차순 정리 후 반환

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

public class Main  {
    static int N;
    static int[][] map;
    static int houseCnt;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    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 tmp = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = tmp.charAt(j)-'0';
            }

        }

        ArrayList<Integer> arr = new ArrayList<>();
        int complexCnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1) {
                    houseCnt = 0;
                    dfs(i, j);
                    arr.add(houseCnt);
                    complexCnt++;
                }
            }
        }
        
        Collections.sort(arr);
        System.out.println(complexCnt);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    static void dfs(int x, int y) {
        map[x][y] = 0;
        houseCnt++;

        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);
        }
    }
}