[java] 스택을 이용한 미로 탐색 알고리즘 구현하기

05 Dec 2023

java

이번에는 스택을 이용하여 미로를 탐색하는 알고리즘을 구현해보겠습니다. 미로는 2차원 배열로 표현되며, 이동 가능한 경로는 0으로 표시되고 벽은 1로 표시됩니다.

다음은 미로 탐색을 위한 알고리즘의 핵심 로직입니다.

시작점을 스택에 Push합니다.
스택이 비어있지 않은 동안 아래 동작을 반복합니다.
1. 스택에서 현재 위치를 Pop합니다.
2. 현재 위치가 목적지인지 확인합니다. 목적지에 도달한 경우 탐색을 종료합니다.
3. 현재 위치에서 이동 가능한 인접한 위치를 찾습니다.
4. 이동 가능한 위치를 스택에 Push합니다.
목적지에 도달하지 못한 경우, 탐색 실패로 간주합니다.

이제 위 알고리즘을 Java로 구현해보겠습니다.

import java.util.Stack;

public class MazeSolver {
    private static 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, 0, 0}};

    public static boolean solve(int startX, int startY, int destX, int destY) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{startX, startY});

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

            // 목적지에 도달한 경우 탐색 종료
            if (x == destX && y == destY) {
                return true;
            }

            // 상하좌우로 이동 가능한 위치를 찾아 스택에 Push
            if (y < maze.length - 1 && maze[y + 1][x] == 0) {
                stack.push(new int[]{x, y + 1}); // 아래로 이동
            }
            if (y > 0 && maze[y - 1][x] == 0) {
                stack.push(new int[]{x, y - 1}); // 위로 이동
            }
            if (x < maze[0].length - 1 && maze[y][x + 1] == 0) {
                stack.push(new int[]{x + 1, y}); // 오른쪽으로 이동
            }
            if (x > 0 && maze[y][x - 1] == 0) {
                stack.push(new int[]{x - 1, y}); // 왼쪽으로 이동
            }
        }

        return false; // 도달하지 못한 경우 탐색 실패
    }

    public static void main(String[] args) {
        int startX = 0;
        int startY = 0;
        int destX = 4;
        int destY = 4;

        if (solve(startX, startY, destX, destY)) {
            System.out.println("미로 탐색 성공!");
        } else {
            System.out.println("미로 탐색 실패!");
        }
    }
}

위 코드를 실행하면 시작점부터 목적지까지 경로를 찾을 수 있는지 여부를 출력합니다.

참고 자료:

Java Stack Documentation