[백준] 2667번: 단지번호 붙이기 - JAVA

문제 링크

BOJ 2667번: 단지번호 붙이기

2667번: 단지번호붙이기

 

풀이 과정

모든 지도를 돌며 연결되어 있는 1을 카운트하며 갯수를 세면 되기 때문에 BFS사용하기로 했다.

 

개인적으로 map을 처리할 때, int형보다 boolean이 처리하기 쉬워서 입력값을 1일 때 true, 0일 때 false로 바꾸어 저장하였다.

이중 반복문을 통해 map배열에 true가 있는지 탐색하고 만약 존재한다면 해당 칸부터 시작해 상하좌우를 탐색하며 queue에 넣으며 방문한 칸을 false로 변경하여 다시 방문하지 않도록 설정하였다. 각 칸을 돌며 단지 수 size++하며 단지 수를 카운트 하였고 list에 add하였다.

 

단지 수가 몇 개가 될지 모르기 때문에 배열이 아닌 LinkedList로 선언하여 집 카운트를 add하는 방식으로 저장하였다. 또한 단지내 집 수를 기준으로 오름차순으로 정렬해야하기 때문에 LinkedList.sort(null)을 활용하여 정렬 해주었다.

 

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] dy = { -1, 1, 0, 0 };
        int[] dx = { 0, 0, -1, 1 };

        Scanner sc = new Scanner(System.in);
        List<Integer> ans = new ArrayList<>();

        int N = sc.nextInt();
        boolean[][] map = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String input = sc.next();

            for (int j = 0; j < N; j++)
                map[i][j] = input.charAt(j) == '1';
        }

        Queue<int[]> que = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!map[i][j])
                    continue;

                que.add(new int[] { i, j });
                map[i][j] = false;
                int size = 0;
                while (!que.isEmpty()) {
                    int[] cur = que.poll();
                    size++;

                    for (int k = 0; k < 4; k++) {
                        int ny = cur[0] + dy[k];
                        int nx = cur[1] + dx[k];

                        if (ny < 0 || nx < 0 || nx >= N || ny >= N || !map[ny][nx])
                            continue;

                        que.add(new int[] { ny, nx });
                        map[ny][nx] = false;
                    }
                }

                ans.add(size);
            }
        }

        System.out.println(ans.size());
        ans.sort(null);
        ans.stream().forEach(System.out::println);

    }
}

 

제출 결과