boj.kr/2667 단지번호붙이기 (silver1) 자바 풀이

1. 모든 좌표를 순회하면서 아래를 반복

1.1. 방문체크하고 집의 개수를 1으로 초기화한 후에 dfs를 수행

1.1.1. 상하좌우 좌표값 중 값이 '1'이고 방문하지 않았으면 방문체크하고 dfs를 호출, 전역변수 d값을 1증감

1.1.2. dfs함수 밖에서 초기화했던 d를 반환

1.2. d_list에 dfs수행 결과 전역변수 d를 추가

1.3. 영역의 개수 cnt를 1 증감

2. 영역의 개수 cnt를 출력하고 d_list를 오름차순으로 출력

 

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

public class Main {

    static int N, d, cnt;
    static int[][] board;
    static boolean[][] visited;
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};

    public static int dfs(int r, int c) {

        for (int i=0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (0<=nr && nr<N && 0<=nc && nc<N) {
                if (board[nr][nc] == 1 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    dfs(nr, nc);
                    d += 1;
                }
            }
        }
        return d;
    }

    public static void main(String[] args) {

        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            N = Integer.parseInt(br.readLine());
            board = new int[N][N];
            visited = new boolean[N][N];

            for (int r=0; r<N; r++) {
                String row = br.readLine();
                for (int c=0; c<N; c++) {
                    board[r][c] = row.charAt(c) - '0';
                }
            }

            List<Integer> d_list = new ArrayList<>();
            for (int r=0; r<N; r++) {
                for (int c=0; c<N; c++) {
                    if (board[r][c] == 1 && !visited[r][c]) {
                        visited[r][c] = true;
                        d = 1;
                        d_list.add(dfs(r, c));
                        cnt += 1;
                    }
                }
            }

            System.out.println(cnt);
            Collections.sort(d_list);
            for(int d : d_list){
                System.out.println(d);
            }

        } catch (Exception e) {
            e.printStackTrace();
        }

    }

}