21.07.28 - [BOJ] 2667. 단지번호붙이기

[suhyunsim]

문제

• 2667

핵심 아이디어

• BFS 문제
• d[i][j] = (i, j) 방문 안했으면 0, 했으면 단지 번호

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q2667;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) {
            String s = sc.nextLine();
            for (int j = 0; j < n; j++) {
                a[i][j] = s.charAt(j) - '0';
            }
        }
        int cnt = 0;
        int[][] group = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i][j] == 1 && group[i][j] == 0) {
                    bfs(a, group, i, j, ++cnt, n);
                }
            }
        }
        int[] ans = new int[cnt];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (group[i][j] != 0) {
                    ans[group[i][j] - 1] += 1;
                }
            }
        }
        Arrays.sort(ans);
        System.out.println(cnt);
        for (int i = 0; i < cnt; i++) {
            System.out.println(ans[i]);
        }
    }

    private static void bfs(int[][] a, int[][] group, int x, int y, int cnt, int n) {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(x, y));
        group[x][y] = cnt;
        while (!queue.isEmpty()) {
            Pair p = queue.remove();
            x = p.x;
            y = p.y;
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (a[nx][ny] == 1 && group[nx][ny] == 0) {
                        queue.add(new Pair(nx, ny));
                        group[nx][ny] = cnt;
                    }
                }
            }
        }
    }
}

class Pair {
    int x;
    int y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}