[소프티어] 장애물 인식 프로그램(JAVA)

문제

https://softeer.ai/practice/6282

---

풀이(11분)

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

public class Main {

    static int n;
    static int[][] arr;
    static Queue<Point> queue = new LinkedList<>();
    static int count = 0;
    static int[] dx = new int[]{0, 0, 1, -1};
    static int[] dy = new int[]{-1, 1, 0, 0};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        List<Integer> list = new ArrayList<>();
        int block = 0;

        for(int i = 0; i < n; i++){
            String line = br.readLine();
            for(int j = 0; j < n; j++){
                arr[i][j] = Integer.parseInt(line.substring(j, j+1));
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(arr[i][j] == 1){
                    block++;
                    count = 1;
                    arr[i][j] = 0;
                    queue.add(new Point(i, j));
                    bfs();
                    list.add(count);
                }

            }
        }

        System.out.println(block);
        Collections.sort(list);
        for(int i : list){
            System.out.println(i);
        }
    }

    static void bfs(){
        while(!queue.isEmpty()){
            Point cur = queue.poll();
            for(int i = 0; i < 4; i++){
                int nextX = cur.x + dx[i];
                int nextY = cur.y + dy[i];
                if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < n){
                    if(arr[nextX][nextY] == 1){
                        arr[nextX][nextY] = 0;
                        count++;
                        queue.add(new Point(nextX, nextY));
                    }
                }
            }
        }
    }

    public static class Point{
        int x;
        int y;

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

---

문제  풀이 전략

 

사방 탐색을 이용한 가장 기본적인 bfs/dfs 문제였다.

방문 배열을 선언하는 것보다 1 -> 0으로 변경하여 방문하지 않게 체크해주는 것이 더좋다고 판단하였다.

 

dfs/bfs : https://to-travel-coding.tistory.com/66

[도구정리] DFS, BFS

사방탐색 : https://to-travel-coding.tistory.com/68

[도구정리] 사방탐색