[Softeer] 장애물 인식 프로그램

문제

I : 1과 0으로 이루어진 정사각형의 배열이 주어진다.

O : 1끼리 붙어있는게 하나의 집합이라고 하고,

     총 몇개의 집합이 있는지 첫 번째 줄에 출력하고,

     집합별로 크기에 따른 오름차순으로 한줄씩 출력하라.

 

문제링크 : https://softeer.ai/practice/info.do?idx=1&eid=409&sw_prbl_sbms_sn=161356

---

원리

반복을 통한 BFS와 오름차순 정렬

---

풀이방법

1. static으로 이중배열을 입력 받는다.

2. 같은 크기의 boolean형 배열 visited를 만들어 준다.

3. 이제 각 배열의 좌표마다 BFS를 돌릴것이다. 이 때 포인트는 값이 1이고, 방문한 적 없는 좌표를 대상으로만.

4. BFS를 돌리는 시작점은 현재 좌표값

5. 이제 대기열에 넣은 좌표값마다 상하좌우를 검사를 한다. 상하좌우 총 4번이며, 검사지점마다 count해준다.

    상하좌우를 표현하기 위해 static in[] 두 개로 좌표값을 변경해주는 테크닉을 사용한다.

6. 각각의 상하좌우에 대해서 검사를 할 것인데, 이때 상하좌우 좌표가 이중배열 범위를 넘어가지 않는게 첫번째 조건

7. 범위를 넘지 않는다면, 이동한 좌표가 1이고 방문한 적이 없을 경우에만 대기열에 다시 넣어줌(다음 이동 검사를 위해)

8. 이때, 이동한 좌표는 방문체크 해줌

9. 대기열의 검사가 다 끝났다는것은 곧 하나의 덩어리가 끝난것이므로, count는 곧 덩어리 크기다. count를 반환

10. BFS 반환값은 덩어리크기별로 모으는 list에 넣는다.

11. list를 오름차순으로 정렬해준다.

12. list의 size = 집합 개수 출력. 그리고 list내 인자들을 순차적으로 출력 

 

---

나의 코드

import java.io.*;
import java.util.*;

public class RecogObstacle {
    static int[] ver = {-1, 1, 0, 0};
    static int[] hor = {0, 0, -1, 1};
    static int[][] matrix;
    static boolean[][] visited;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        matrix = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String[] arr = br.readLine().split("");
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(arr[j]);
            }
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 1 && !visited[i][j]) {
                    list.add(BFS(i, j));
                }
            }
        }
        bw.write("" + list.size() + "\n");
        list.sort(Comparator.naturalOrder());
        for (int i = 0; i < list.size(); i++) bw.write("" + list.get(i) + "\n");

        bw.close();
    }

    private static int BFS(int nowI, int nowJ) {
        Deque<Node> dq = new ArrayDeque<>();
        dq.add(new Node(nowI, nowJ));
        int count = 0;
        while (!dq.isEmpty()) {
            Node now = dq.poll();
            count++;
            visited[now.Y][now.X] = true;

            for (int dir = 0; dir < 4; dir++) {
                int nowY = now.Y + ver[dir];
                int nowX = now.X + hor[dir];

                if (0 <= nowY && nowY < N && 0 <= nowX && nowX < N) {
                    if (matrix[nowY][nowX] == 1 && !visited[nowY][nowX]) {
                        dq.add(new Node(nowY, nowX));
                        visited[nowY][nowX] = true;
                    }
                }
            }
        }
        return count;
    }

    private static class Node {
        private int Y;
        private int X;

        public Node(int Y, int X) {
            this.Y = Y;
            this.X = X;
        }
    }
}