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

1. 문제

Softeer

자율주행팀 SW 엔지니어인 당신에게 장애물과 도로를 인식할 수 있는 프로그램을 만들라는 업무가 주어졌다.

 

[그림 1] 지도 예시

우선 [그림 1]과 같이 정사각형 모양의 지도가 있다. 1은 장애물이 있는 곳을, 0은 도로가 있는 곳을 나타낸다.

 

당신은 이 지도를 가지고 연결된 장애물들의 모임인 블록을 정의하고, 불록에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 장애물이 좌우, 혹은 아래위로 붙어 있는 경우를 말한다. 대각선 상에 장애물이 있는 경우는 연결된 것이 아니다.

 

[그림 2] 블록 별 번호 부여

 

[그림 2]는 [그림 1]을 블록 별로 번호를 붙인 것이다. 

 

지도를 입력하여 장애물 블록수를 출력하고, 각 블록에 속하는 장애물의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

---

2. 풀이

기본적인 BFS문제라서 코드를 메서드별로 분리하는 데 더 신경썼다.

char[][] board	입력받은 지도
int N	지도 크기
int[][] deltas	움직일 수 있는 방향

 

isValid

board범위 내에 있는지, 방문한 적 있는지 체크하는 메서드다.

public static boolean isValid(int i, int j){
    return i>=0 && j>=0 && i<N && j<N && board[i][j]=='1';
}

 

BFS

방문처리는 '1'을 '0'으로 바꾸는걸로 대신했다. 지금 생각해보니 '2'나 '*'등 다른 문자로도 표현해도 됐을 것 같다.

1.  위치 i,j를 입력받은 후 그 위치부터 bfs 탐색을 진행한다. 

2.  탐색 전 최초위치를 '0'으로 바꾸는 것도 잊지 않아야 한다.

3.  queue가 빌 때까지 반복하는데, 반복 한 번 할 때마다 count를 1씩 추가해서 몇 개의 장애물이 있는지 저장한다.

4.  다음 위치를 찾을 때 isValid 메서드를 사용한다. 방문할 수 있는 곳이라면 queue에 다음 위치를 넣고, board 값을 '0'으로 변경한다.

5.  마지막에 count를 반환한다.

public static int bfs(int i, int j){
    int count = 0;
    Queue<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[]{i,j});
    board[i][j] = '0';

    int[] now;
    int ni,nj;
    while(!queue.isEmpty()){
        count++;
        now = queue.poll();

        for(int[] d:deltas){
            ni = now[0] + d[0];
            nj = now[1] + d[1];
            if(isValid(ni,nj)){
                queue.offer(new int[]{ni,nj});
                board[ni][nj] = '0';
            }
        }
    }

    return count;
}

 

Main

1.  N을 입력받고, toCharArray()메서드를 이용해서 board 한 줄을 한 번에 입력했다.

2.  ArrayList를 만들어서 한 블록당 몇 개의 장애물이 있는지 저장했다.

3.  board를 처음부터 끝까지 탐색하면서, 장애물이 있다면 bfs메서드를 실행한 뒤 그 결과값을 count에 더했다.

4.  StringBuilder를 사용했다. 리스트의 사이즈로 몇 개의 블록이 있는지 알 수 있다. count.size를 더한다.

5.  count를 오름차순으로 정렬한 뒤, 순차적으로 하나씩 sb에 더한다.

6.  sb를 출력한다.

public static void main(String args[]) throws Exception {
    //입력
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(in.readLine());
    board = new char[N][N];
    for(int i=0;i<N;i++){
        board[i] = in.readLine().toCharArray();
    }

    //탐색
    ArrayList<Integer> count = new ArrayList<>();
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(board[i][j]=='1'){
                count.add(bfs(i,j));
            }
        }
    }

    //출력
    StringBuilder sb = new StringBuilder();
    sb.append(count.size()).append('\n');
    Collections.sort(count);
    for(int cnt:count){
        sb.append(cnt).append('\n');
    }
    System.out.print(sb);
}

 

전체 코드

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

public class Main
{
    static char[][] board;
    static int N;
    static int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1}};
    public static void main(String args[]) throws Exception
    {
        //입력
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(in.readLine());
        board = new char[N][N];
        for(int i=0;i<N;i++){
            board[i] = in.readLine().toCharArray();
        }

        //탐색
        ArrayList<Integer> count = new ArrayList<>();
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(board[i][j]=='1'){
                    count.add(bfs(i,j));
                }
            }
        }

        //출력
        StringBuilder sb = new StringBuilder();
        sb.append(count.size()).append('\n');
        Collections.sort(count);
        for(int cnt:count){
            sb.append(cnt).append('\n');
        }
        System.out.print(sb);
    }

    public static int bfs(int i, int j){
        int count = 0;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{i,j});
        board[i][j] = '0';

        int[] now;
        int ni,nj;
        while(!queue.isEmpty()){
            count++;
            now = queue.poll();

            for(int[] d:deltas){
                ni = now[0] + d[0];
                nj = now[1] + d[1];
                if(isValid(ni,nj)){
                    queue.offer(new int[]{ni,nj});
                    board[ni][nj] = '0';
                }
            }
        }

        return count;
    }

    public static boolean isValid(int i, int j){
        return i>=0 && j>=0 && i<N && j<N && board[i][j]=='1';
    }
}

---

3. 결과