자바 코딩테스트 강좌, 미로 탐색하기

코딩 인터뷰 및 알고리즘 테스트는 여러 후보자들에게 흔히 있는 도전 과제입니다. 그 중 하나인 미로 탐색 문제는 매우 인기 있는 알고리즘 문제로, BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)와 같은 탐색 알고리즘을 배우기에 적합합니다. 본 글에서는 자바를 사용하여 미로를 탐색하는 문제를 살펴보고, 이를 해결하기 위한 단계별 접근 방법을 설명하겠습니다.

문제 설명

주어진 2차원 배열에서, 0은 이동할 수 있는 공간을, 1은 벽을 나타냅니다. 시작 지점에서 도착 지점까지의 경로를 찾는 것입니다. 경로가 존재하면 그 경로를 출력하고, 존재하지 않으면 “경로가 없습니다.”라고 출력합니다.

문제 예시

    입력:
    [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0]
    ]
    시작 지점 (0, 0)
    도착 지점 (4, 4)

    출력:
    (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (3, 2) -> (4, 2) -> (4, 3) -> (4, 4)

해결 과정

1. 문제 이해하기

우선적으로 문제를 정확하게 이해해야 합니다. 미로를 표현하는 2차원 배열에서, 시작 지점에서 출발해 도착 지점까지 가는 경로를 찾아야 하며, 벽(1)을 지나서는 안 됩니다. 위의 예시에서는 시작 지점에서 도착 지점까지 어떤 경로를 통해 갈 수 있는지를 알아내야 합니다.

2. 탐색 알고리즘 선택하기

미로 탐색은 BFS 또는 DFS로 해결할 수 있습니다. BFS는 최단 경로를 찾는 데 유리하며, DFS는 경로를 깊게 탐색하는 데 유리합니다. 여기서는 BFS를 이용한 해결 방법을 선택하겠습니다.

3. 알고리즘 설계

BFS 알고리즘을 사용하여 다음과 같은 절차로 경로를 탐색할 것입니다:

시작 지점에서 이웃한 지점을 큐에 추가합니다.
큐에서 지점을 하나씩 꺼내면서, 해당 지점이 도착 지점인지 확인합니다.
도착 지점이 아닌 경우, 그 지점의 이웃한 지점들을 큐에 추가합니다.
모든 경로를 탐색해도 도착 지점에 도달하지 못했다면, “경로가 없습니다.”라고 출력합니다.

4. 자바 코드 구현하기

    import java.util.LinkedList;
import java.util.Queue;

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

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        int[][] maze = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0}
        };
        
        findPath(maze, new Point(0, 0), new Point(4, 4));
    }

    static void findPath(int[][] maze, Point start, Point end) {
        int n = maze.length;
        int m = maze[0].length;
        boolean[][] visited = new boolean[n][m];
        Point[][] previous = new Point[n][m];

        Queue queue = new LinkedList<>();
        queue.offer(start);
        visited[start.x][start.y] = true;

        while (!queue.isEmpty()) {
            Point current = queue.poll();
        
            if (current.x == end.x && current.y == end.y) {
                printPath(previous, start, end);
                return;
            }

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

                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && maze[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    previous[nx][ny] = current;
                    queue.offer(new Point(nx, ny));
                }
            }
        }

        System.out.println("경로가 없습니다.");
    }

    static void printPath(Point[][] previous, Point start, Point end) {
        StringBuilder path = new StringBuilder();
        for (Point at = end; at != null; at = previous[at.x][at.y]) {
            path.insert(0, String.format("-> (%d, %d) ", at.x, at.y));
        }
        System.out.println(path.substring(4)); // 처음의 "-> " 제거
    }
}

5. 코드 설명

위의 코드에서는 BFS 알고리즘을 구현하였습니다. Point라는 내부 클래스를 사용해 (x, y) 좌표를 정의하여 큐와 경로 추적에 활용합니다. 큐에는 현재 위치의 이웃 좌표를 추가하며, 방문한 지점은 visited 배열에서 체크하여 중복 탐색을 방지합니다. 도착 지점에 도달하면, printPath 메서드가 호출되어 경로를 출력합니다.

6. 코드 실행 결과

    (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (3, 2) -> (4, 2) -> (4, 3) -> (4, 4)

마무리

이제 미로 탐색 문제를 해결하는 방법에 대해 배우셨습니다. 이 알고리즘은 다양한 문제에 적용할 수 있는 유용한 기술입니다. 문제를 해결하기 위해 탐색 알고리즘의 기초를 이해하고, 이를 자바로 구현하는 과정은 매우 유익한 경험이 될 것입니다. 여러분의 코딩 테스트 준비에 도움이 되길 바랍니다!