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

 

 

문제 

0과 1로 이루어진 지도가 주어진다.

0은 집이 없는 곳 1은 집이 있는 곳이라 하고 집이 상하좌우로 모여있는 곳을 하나의 단지로 설정한다.

단지의 총 개수와 단지에 속하는 집의 수를 오름차순으로 정렬해서 출력해라.

(5 <= 지도크기 N <= 25)

 

 

코드 

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

public class b2667 {
    static int N;
    static int[][] map;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1){
                    result.add(bfs(i, j));
                }
            }
        }

        int cnt = 0;
        Collections.sort(result);
        for (Integer r : result) {
            cnt++;
            sb.append(r).append("\n");
        }
        System.out.println(cnt);
        System.out.println(sb);
    }

    static int bfs(int x, int y) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        map[x][y] = -1;
        int cnt = 1;

        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = point[0] + dx[i];
                int ny = point[1] + dy[i];
                if (isRange(nx, ny) && map[nx][ny] == 1) {
                    queue.add(new int[]{nx, ny});
                    map[nx][ny] = -1;
                    cnt++;
                }
            }
        }

        return cnt;
    }

    static boolean isRange(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N)
            return false;
        return true;
    }
}

 

 

채점 결과