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

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

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

1. 이중 for문으로 map 전체를 확인하면서 방문하지 않았고 동시에 1인 곳부터 BFS 탐색을 시작합니다.

2. 한번의 BFS 탐색이 끝나면 하나의 단지가 모두 check됩니다. 총 단지의 수를 의미하는 apart라는 변수를 사용해서 map[row][col] = apart 대입하고 apart를 증가시킵니다.

3. 즉, 한번의 BFS를 통해 인접한 집들을 하나의 단지로 모두 check하고 단지를 의미하는 apart 변수를 통해 총 몇개의 단지가 있는지 확인할 수 있습니다.

4. 1번이 모두 끝났으면 다시 이중 for문을 통해 map[row][col] 값을 체크해서 값이 1이면 1단지, 2이면 2단지,

n이면 n단지로 카운트합니다.

5. 각 배열의 index에 저장된 값이 (index + 1)단지의 수 이므로 Arrays.sort()를 통해 오름차순으로 정렬한 뒤

값을 출력합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
    public static int[] dirX = { 0, 0, -1, 1 };
    public static int[] dirY = { -1, 1, 0, 0 };
    public static int[][] map;
    public static boolean[][] visited;
    public static int N, apart = 1;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];
 
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(str.charAt(j) + "");
            }
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && map[i][j] != 0) {
                    bfs(i, j);
                    apart += 1;
                }
            }
        }
 
        int[] ans = new int[apart - 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] != 0) {
                    ans[map[i][j] - 1] += 1;
                }
            }
        }
        
        
        Arrays.sort(ans);
        System.out.println(apart - 1);
        for (int num : ans)
            System.out.println(num);
 
    }
 
    public static void bfs(int startRow, int startCol) {
 
        Queue<Node> q = new LinkedList<Node>();
        visited[startRow][startCol] = true;
        map[startRow][startCol] = apart;
        q.offer(new Node(startRow, startCol));
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
 
            for (int i = 0; i < 4; i++) {
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc) && !visited[nr][nc] && map[nr][nc] != 0) {
                    visited[nr][nc] = true;
                    map[nr][nc] = apart;
                    q.offer(new Node(nr, nc));
                }
            }
        }
 
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
 
}
 
class Node {
 
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
}