백준 - 너비 우선 탐색 - 2667번

백준 문제 1012번 문제가 비슷한 유형으로 추가적으로 연속적인 1의 개수도 구하는 문제이다.

같은 영역의 단지에 번호를 붙이고 해당 영역의 칸의 수를 출력하는 문제이다. 

여기서 전체 단지의 수를 저장하는 변수 + 각 단지의 칸의 수를 저장하는 배열이 필요하다. 

---

1. 입력받을 변수를 선언하고 input 배열을 선언한다. 추가적으로 해당 칸을 방문했는지 확인하기 위한 visited 배열을 선언한다. 

2. input 배열을 입력받으며 visited 배열값을 false 로 초기화한다.

3. 입력 받은 후 BFS 알고리즘을 실행한다 (이전 1012번 문제와 동일)

4. BFS 알고리즘에 추가적으로 상하좌우에 해당하는 인덱스 위치값을 큐에 넣는 과정에서 단지의 칸수를 세는 count 값을 증가시킨다. 

5. 모든 while 문이 끝나 BFS 알고리즘을 벗어날 때 전체 단지의 수를 증가하고 + count 값을 배열에 넣는다. 

6. 마지막으로 단지의 수를 출력하고 문제에서 "각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오." 라고 작성되어 있기에 count 값이 있는 배열을 오름차순으로 정렬한 후 순서대로 출력한다. 
-> 이 부분 때문에... 사알짝 고생했다ㅜㅜ..

 

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class No_2667 {
    static int n;
    static int input[][];
    static Boolean visit[][];
    static int total;
    static Queue<Integer> cnt;
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0,-1};

    public static void main (String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        n = Integer.parseInt(st.nextToken());
        input = new int[n][n];
        visit = new Boolean[n][n];
        cnt = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(bf.readLine());
            String str = st.nextToken();
            for (int j = 0; j < n; j++) {
                input[i][j] = Integer.parseInt(str.substring(j, j+1));
                visit[i][j] = false;
            }
        }

        for (int i =0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j] && input[i][j] == 1) {
                    BFS(i,j);
                }
            }
        }
        System.out.println(total);
        int temp[] = new int[total];

        for (int i = 0; i < total; i++) {
            temp[i] = cnt.poll();
        }
        Arrays.sort(temp);
        for (int i = 0; i < total; i++) {
            System.out.println(temp[i]);
        }
    }

    private static void BFS(int a, int b) {
        Queue<int[]> queue = new LinkedList<>();
        visit[a][b] = true;
        queue.offer(new int[] {a,b});
        int count = 1;
        while (!queue.isEmpty()){
            int now[] = queue.poll();

            for (int k = 0; k < 4; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if (x >= 0 && y >= 0 && x < n && y < n) {
                    if(!visit[x][y] && input[x][y] == 1) {
                        visit[x][y] = true;
                        queue.offer(new int[] {x,y});
                        count++;
                    }
                }
            }
        }
        total++;
        cnt.offer(count);
    }
}