[Algorithm] BFS 문제 풀이 - 미로 탈출 (자바코드)

BFS 문제 풀이 - 미로 탈출 (자바코드)

 

'이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책에서 DFS&BFS 알고리즘 문제 중 '미로 탈출' 문제와 풀이를 설명합니다. 코드는 자바로 작성합니다.

 

문제

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

🎁입력 조건

• 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다.

각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다. 

 

🎊출력 조건

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

🎁입력 예시

5 6

101010

111111

000001

111111

111111

 

🎊출력 예시

10

문제 해설

처음한 문제 접근은 BFS 알고리즘을 만들어 경로를 탐색하고, count 변수를 만들어 움직일 때마다 1씩 더하는 방식이었다. 하지만, 경로가 여러 갈래로 나뉠 수 있으므로 이는 틀린 접근 방식이었다.

 

최소 경로를 구하는 다음 문제는 BFS를 이용하면 효과적이다. BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다.

 

움직일 수 있는 경로는 상하좌우이므로, 현재 위치에서 상하좌우 방향으로 이동할 수 있는 지 확인한다. 움직을 수 있고, 해당 노드에 처음 방문하는 경우  움직이기 전 노드의 값에서 1 더해 입력한다. 이때 BFS 알고리즘 탐색이 종료되면 (N,M) 좌표의 값을 출력한다. 

 

 

문제 풀이(자바) 

public class 미로탈출 {
    public static int N, M;
    // N, M의 값에 맞춰 200,200 크기의 배열을 만들면, 이동 좌표 계산시 array boundary exceeded가 발생할 수 있다.
    public static int [][]graph = new int[201][201]; 

    //이동할 네 가지 방향 정의 {상, 하, 좌 ,우}
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};

    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine();

        int result = 0;
        for(int i=0; i<N; i++){
            String line = sc.nextLine();
            for(int j=0; j<M; j++){
                graph[i][j] = line.charAt(0) - '0';
            }
        }

        //BFS 수행 결과 출력
        System.out.println(bfs(0,0));
    }

    public static int bfs(int x, int y){
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(1,1));

        //큐가 빌 때까지 반복
        while(!queue.isEmpty()){
            Node node = queue.poll();
            x = node.getX();
            y = node.getY();

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

                //미로 범위를 벗어나면 무시
                if(nx <0 || ny < 0 || nx >= N || ny >= M) continue;
                //한 번 왔던 위치면 무시 , 괴물이 있는 위치면 무시
                if(graph[nx][ny]==1){
                    graph[nx][ny] = graph[x][y] + 1;
                    queue.add(new Node(nx, ny));
                }
            }
        }
        // 가장 오른쪽 아래까지의 최단 거리 반환
        return graph[N-1][M-1];
    }

    static class Node{
        final private int x;
        final private int y;
        private int value;

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

        public int getX() {
            return x;
        }

        public int getY(){
            return y;
        }
    }
}

 

출처

github.com/ndb796/python-for-coding-test/blob/master/5/11.java