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

Softeer

 

 

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


public class Main
{
    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int N;
    static char[][] map;
    static int[][] visited;
    static int cnt;
    static int[] dx = { 1, 0, -1, 0 }, dy = { 0, 1, 0, -1 };
    static List<Integer> blocks;

    private static void solution() {
        blocks = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == '0' || visited[i][j] > 0) continue;
                cnt += 1;
                bfs(j, i);
            }
        }
    }

    private static void bfs(int x, int y) {
        visited[y][x] = cnt;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        int num = 1;

        while(!queue.isEmpty()) {
            Point cur = queue.poll();
            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (visited[ny][nx] > 0 || map[ny][nx] == '0') continue;
                visited[ny][nx] = cnt;
                num += 1;
                queue.offer(new Point(nx, ny));
            }
        }
        blocks.add(num);
    }
    
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        visited = new int[N][N];

        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        solution();
        sb.append(cnt).append("\n");
        Collections.sort(blocks);
        for (int i = 0; i < blocks.size(); i++) {
            sb.append(blocks.get(i)).append("\n");
        }

        br.close();
        System.out.println(sb.toString());
    }
}