백준 2667 (단지번호붙이기)

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    static int N; // 지도의 크기
    static int[][] arr; // 입력 받은 단지
    static boolean[][] visited; // 단지 체크
    static List<Integer> result; // 단지내 집의 수 모음
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    static int each = 0; // 단지내 집의 수

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        arr = new int[N][N];
        visited = new boolean[N][N];
        result = new ArrayList<>();

        for(int j=0; j<N; j++) {
            String s = br.readLine();
            for(int i=0; i<s.length(); i++) {
                arr[j][i] = Character.getNumericValue(s.charAt(i));
            }
        }

        for(int j=0; j<N; j++) {
            for(int i=0; i<N; i++) {
            // 현재 위치가 1이고, 처음 방문할 경우
                if(arr[j][i] == 1 && visited[j][i] == false) {
                    visited[j][i] = true; // 방문 처리
                    each = 0; // dfs 돌기전에 단지 초기화
                    dfs(j, i);
                    result.add(each);

                }
            }
        }
        Collections.sort(result);

        bw.write(result.size() + "\n");
        for(int r : result) bw.write(r + "\n");
        bw.flush();
        bw.close();
    }

    static void dfs(int y, int x) {
        for(int k=0; k<4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

			// 다음 좌표가 지도 안에 존재할 경우
            if(nx >= 0 && ny >= 0 && nx < N && ny < N) {
            	// 다음 좌표가 1이고, 첫 방문일 경우
                if(arr[ny][nx] == 1 && ! visited[ny][nx]) {
                    visited[ny][nx] = true; // 방문 처리
                    dfs(ny, nx); // 재귀 함수 호출
                }
            }
        }
        each++; // 현재 단지의 집 +1
    }
}

https://www.acmicpc.net/problem/2667

 

2667번: 단지번호붙이기