[소프티어] 장애물 인식 프로그램 레벨2 자바 풀이 (DFS, BFS)

https://softeer.ai/practice/6282

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

 

딱 문제를 보자마자 떠오른것은 DFS

정답 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    private static int n;
    private static int blockCount;
    private static int[][] map;
    private static int[][] visited;
    private static int[] dy = {-1, 1, 0, 0};
    private static int[] dx = {0, 0, -1, 1};
    private static ArrayList<Integer> blocks = new ArrayList<>();


    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());
        map = new int[n][n];
        visited = new int[n][n];

        // Map 입력 받기
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        // dfs 실행 부
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1 && visited[i][j] == 0) {
                    blockCount = 0;
                    dfs(i, j);
                    blocks.add(blockCount);
                }
            }
        }

        // blocks 오름차순
        Collections.sort(blocks);


        // 정답 출력
        bw.write(blocks.size() + "\n");
        for (int block : blocks) {
            bw.write(block + "\n");
        }

        bw.flush();
        bw.close();
    }

    public static void dfs(int y, int x) {

        // 방문 표시
        visited[y][x] = 1;

        // block 개수 증가
        blockCount++;

        // 상하좌우 확인
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            // 범위를 벗어나는 경우 제외
            if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;

            // '0'인 경우 제외
            if (map[ny][nx] == 0) continue;

            // 방문한 경우 제외
            if (visited[ny][nx] != 0) continue;

            // dfs 재귀
            dfs(ny, nx);
        }
    }
}

DFS를 해봤다면 기본적인 문제에 해당하는것 같다.

다만 아직 JAVA 코테에 익숙하지 않아 몰랐던 정렬 같은것은 추가적으로 알게 되었다.

ArrayList 정렬

이전에는 lambda로 객체의 속성으로 정렬 했다면 이번에는 단일값을 가진 Integer 리스트를 정렬했다.

Collections.sort(list): 오름차순으로 정렬

Collections.sort(list, Collections.reverseOrder()): 내림차순으로 정렬

 

BFS

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

public class Main {
    private static int n;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[] dy = {-1, 1, 0, 0};
    private static int[] dx = {0, 0, -1, 1};
    private static ArrayList<Integer> list = new ArrayList<>();
    private static int blockCount;


    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());
        map = new int[n][n];
        visited = new boolean[n][n];

        // Map 입력 받기
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        // BFS
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    // bfs
                    blockCount = 0;
                    bfs(i, j);
                    list.add(blockCount);
                }
            }
        }

        Collections.sort(list);

        bw.write(list.size() + "\n");
        for (int i : list) {
            bw.write(i + "\n");
        }

        bw.flush();
        bw.close();
    }

    public static void bfs(int startY, int startX) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startY, startX});
        // 방문 표기
        visited[startY][startX] = true;
        blockCount++;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int y = current[0];
            int x = current[1];

            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];

                // 범위 체크
                if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;

                // 0 인 경우, 방문 여부 체크
                if (map[ny][nx] == 0 || visited[ny][nx]) continue;

                queue.add(new int[]{ny, nx});
                visited[ny][nx] = true;
                blockCount++;
            }
        }

    }
}

BFS로도 풀 수 있다! 연습 삼아 풀기 좋은 문제~