미로 탈출 문제

'이것이 취업을 위한 코딩 테스트다 with 파이썬' 의 수록된 문제를 풀어 보겠습니다.

문제 제목은 '미로 탈출' 문제 입니다.

 

이것이 취업을 위한 코딩 테스트다 with 파이썬

2차원 미로 속의 값이 0인 칸은 피하고, 1인 칸으로 만 이동해서, 출발점 : (0, 0), 도착점 : (N * M) 까지의 최소칸의 갯수를 구하는 문제 입니다.

 

구현하기 전에 먼저 고민 했습니다.

1. BFS와 DFS를 이용해서 탐색을 하는데, 최소 칸은 어떻게 구할수 있을지...

2. BFS와 DFS를 모두 구현하고, 둘 중 더 최소가 되는 칸 수를 출력 해줘야 하는지...

 

하지만, 이건 틀린 접근 방법 이였고, BFS와 predecessor를 이용하는 접근 방법으로 풀 수 있었습니다. 저는 처음에 predecessor를 생각 못하고, 계속 BFS를 이용해서 방문 노드를 카운트 하는 방법으로 해결 할려고 했습니다. 

 

 

2. Java 소스 코드

 

public static void main(String[] args) {
        int N = 5, M = 6;
        int[][] array = {
                {1, 0, 1, 0, 1, 0},
                {1, 1, 1, 1, 1, 1},
                {0, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 1}
        };
        int answer = new Page152_2().solution(N, M, array);
        System.out.print(answer);
}

 

public int solution(int N, int M, int[][] graph){
        int distance = new BFS(N, M, graph).search(0, 0);
        for (int[] x : graph) {
            for (int y : x) {
                System.out.printf("%3d ", y);
            }
            System.out.println();
        }

        System.out.println();
        return distance;
    }

 

class BFS{
    private int N;
    private int M;
    private int[][] graph;

    // (0, 0)인 자기 자신을 제외한 주변 노드 방문을 위해
    private int[] dx = {-1, 1, 0, 0};
    private int[] dy = {0, 0, -1, 1};

    public BFS(int N, int M, int[][] graph) {
        this.N = N;
        this.M = M;
        this.graph = graph;
    }

    public int search(int n, int m){
        Queue<Node> queue = new LinkedList<>();

        queue.offer(new Node(n, m));
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            int x = cur.getX();
            int y = cur.getY();

            // 주변 노드들을 bfs 한다.
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 범위를 넘기지 않는다.
                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

                // 괴물이 존재 하는 경우 가지 않는다.
                if (graph[nx][ny] == 0) continue;

                // 처음 방문 하는 노드만 거리 기록
                if (graph[nx][ny] == 1){
                    // 최단 거리를 구하기 위해서는 이전 노드 + 1 (predecessor 이용)
                    // count 변수를 만들어 +1 하는 방법은
                    // bfs 는 모든 노드를 탐방하기 때문에
                    // 1이 들어 있는 모든 노드의 갯수를 반환
                    graph[nx][ny] = graph[x][y] + 1;
                    queue.offer(new Node(nx, ny));
                }
            }
        }
        // 도착지점 값 반환
        return graph[N-1][M-1];
    }
}

 

여기서, 제가 헷갈렸던 부분은 graph[nx][ny] = graph[x] + graph[y] + 1; 을 사용하지 않고 count 변수를 이용해서 최소 칸의 갯수를 출력 할수 있지 않을까 생각 했습니다. 하지만 BFS 특성상 모든 칸을 다 카운트 하므로, 이것은 틀린 접근 방법이고, 대신 이전 노드의 거리 값을 +1 증가하며 BFS 탐색을 끝내고, graph[N-1][M-1]의 값을 반환 하도록 구현 하였습니다.

 

 

class Node{
    private int x;
    private int y;

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

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

 

처음에는 큐의 미로의 칸을 기억할 수 있는 1차원 배열을 만들어서, 이 1차원 배열로 구현을 하려고 애썼지만, 이렇게 x, y값을 담는 자료구조를 사용하면, 2차원 graph의 맞게 BFS 탐색을 할수 있었습니다.