그래프 / 백준 2667 단지 번호 붙이기

문제 접근

boolean 이중 배열 사용

>> 1이면 true값 부여, true 만나면 dfs 시작 상하좌우 확인

 

DFS 사용

>> 한번 끝나면 단지 갯수 + 1 (트리 dfs 연결 요소 갯수 구할때 느낌)

>> 각 단지의 집 수는 따로 cnt로 세고 ArrayList에 저장

 

DFS 안에서 상하좌우의 움직임을 표현할 때

>> dx, dy의 int배열 값과  for문 사용

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class S2667 {
    static boolean[][] visit;
    static int cnt, N;
    static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    static StringBuilder sb = new StringBuilder();

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

        N = Integer.parseInt(br.readLine());
        visit = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < N; j++) {
                if (s.charAt(j) == '1') {
                    visit[i][j] = true;
                }
            }
        }

        int total = 0;
        ArrayList<Integer> cntarr = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visit[i][j]) {
                    cnt = 0;
                    dfs(i, j);
                    cntarr.add(cnt);
                    total++;
                }
            }
        }
        sb.append(total).append("\n");

        Collections.sort(cntarr);
        for (int val : cntarr) {
            sb.append(val).append("\n");
        }

        System.out.println(sb);
    }

    static void dfs(int y, int x) {
        visit[y][x] = false;
        cnt++;

        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= N || yy < 0 || xx >= N || xx < 0 || !visit[yy][xx]) {
                continue;
            }
            dfs(yy, xx);
        }
    }
}