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

장애물 인식 프로그램 문제 바로가기

풀이 

전형적인 탐색문제이다.
DFS, BFS 원하는 방식으로 풀면 될 것 같다.
전체를 한번씩 순회하해야 되니까 중복 방문 방지를 위한 방문체크(visited) 가 필요하고,
순회할때마다 카운팅을 해서 마지막에 오름차순 후 출력해주면 된다.

import java.util.*;
import java.io.*;
import java.util.stream.IntStream;


public class Main {

    private static int N;
    private static int[][] arr;
    private static boolean[][] visited;
    private static List<Integer> hurdleAreaCountList = new ArrayList<>();
    private static int areaCount;

    private static final int[] moveX = {-1, 1, 0, 0};
    private static final int[] moveY = {0, 0, -1, 1};

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

        for (int i = 0; i < N; i++) {
            char[] ch = br.readLine().toCharArray();
            for (int j = 0; j < N ; j++) {
                if (ch[j] == '0') continue;
                arr[i][j] = 1;
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(visited[i][j] || arr[i][j] == 0) continue;
                areaCount = 1;
                dfs(i, j);
                hurdleAreaCountList.add(areaCount);
            }
        }
        Collections.sort(hurdleAreaCountList);

        System.out.println(hurdleAreaCountList.size());
        hurdleAreaCountList.forEach(System.out::println);
    }

    private static void dfs(int x, int y) {
        visited[x][y] = true;


        for (int i = 0; i < 4; i++) {
            int mx = x + moveX[i];
            int my = y + moveY[i];
            if(mx < 0 || my < 0 || mx >= N || my >= N || arr[mx][my] == 0 || visited[mx][my]) continue;
            areaCount++;
            dfs(mx, my);
        }

    }


}