[Baekjoon Online Judge] 2667번: 단자번호붙이기

2667번: 단지번호붙이기

요구사항

 - 1은 집이 있는 곳, 0은 집이 없는 곳을 나타낸다.

 - 집의 모임인 단지를 정의한다.

 - 단지에 번호를 붙인다.

 - 단지가 연결되었다는 것은 상하좌우에 다른 집이 있는 경우이다.

 - 대각선 상에 집은 연결된 것이 아니다.

입력 

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

---

 이전 문제인 미로 찾기의 BFS를 거의 비슷하게 활용한 문제이다.

[Baekjoon Online Judge] 2178번: 미로 탐색

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Baekjoon2667 {

    static int[][] matrix;
    static boolean[][] visited;
    static int n;
    static int count;
    static int[] apartments;

    static class Location {
        int x, y;
        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void bfs(int startX, int startY) {
        Queue<Location> queue = new LinkedList<>();
        queue.add(new Location(startX, startY));
        visited[startX][startY] = true;
        ++apartments[count];

        //             상, 하, 좌, 우
        int[] xMove = {-1, 1, 0, 0};
        int[] yMove = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            Location location = queue.poll();
            int row = location.x;
            int col = location.y;

            for (int i = 0; i < 4; i++) { // 상하좌우 4방향 탐색
                int x = row + xMove[i];
                int y = col + yMove[i];

                if (isLocation(x, y)) {
                    queue.add(new Location(x, y));
                    visited[x][y] = true;
                    ++apartments[count];
                }
            }
        }
    }

    public static boolean isLocation(int x, int y){
        if(x < 1 || x > n || y < 1 || y > n) return false;
        if(visited[x][y] != false || matrix[x][y] == 0) return false;
        return true;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(bufferedReader.readLine());
        count = 0;
        apartments = new int[(n + 1) * (n + 1)];
        matrix = new int[(n + 1)][(n + 1)];
        visited = new boolean[(n + 1)][(n + 1)];

        for(int i = 1; i <= n; i++){
            String row = bufferedReader.readLine();
            for(int j = 1; j <= n; j++) {
                matrix[i][j] = row.charAt(j - 1) - '0';
            }
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(matrix[i][j] == 1 && !visited[i][j]){
                    ++count;
                    bfs(i,j);
                }
            }
        }

        Arrays.sort(apartments);

        bufferedWriter.write(count + "\n");
        for (int i = 0; i < apartments.length; i++) {
            if(apartments[i] != 0) bufferedWriter.write(apartments[i] + "\n");
        }

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}