[java] 자바 스택을 활용한 미로 찾기 알고리즘 구현하기

05 Dec 2023

java

이번 포스트에서는 자바 프로그래밍 언어를 사용하여 스택을 활용한 미로 찾기 알고리즘을 구현하는 방법을 알아보겠습니다.

1. 스택(Stack) 이란?

스택은 후입선출(LIFO - Last-In, First-Out) 구조를 가지는 자료구조로, 데이터를 저장하고 꺼내는 작업이 가능합니다. 가장 최근에 저장된 데이터가 가장 먼저 꺼내지는 특성을 가지고 있습니다.

2. 미로 찾기 알고리즘

미로 찾기 알고리즘은 출발점에서 도착점까지의 최단 경로를 찾는 문제입니다. 이 알고리즘은 대부분 깊이 우선 탐색(DFS - Depth-First Search)을 활용하여 구현됩니다. 스택을 사용하여 깊이 우선 탐색을 구현할 수 있습니다.

import java.util.Stack;

public class MazeSolver {

    public static void main(String[] args) {
        int[][] maze = {
            {0, 0, 0, 0, 0},
            {1, 1, 0, 1, 0},
            {0, 0, 0, 0, 0},
            {0, 1, 1, 1, 1},
            {0, 0, 0, 0, 0}
        };
        
        solveMaze(maze);
    }
    
    private static void solveMaze(int[][] maze) {
        Stack<int[]> stack = new Stack<>();
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        
        int[] start = {0, 0};
        int[] end = {maze.length - 1, maze[0].length - 1};
        
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int[] current = stack.pop();
            int row = current[0];
            int col = current[1];
            
            visited[row][col] = true;
            
            if (row == end[0] && col == end[1]) {
                System.out.println("도착점에 도착했습니다.");
                return;
            }
            
            // 상하좌우 이동
            if (row - 1 >= 0 && maze[row - 1][col] == 0 && !visited[row - 1][col]) {
                int[] up = {row - 1, col};
                stack.push(up);
            }
            
            // ...
            
            // 다른 이동 방향에 대한 로직
            
        }
        
        System.out.println("미로를 탈출할 수 없습니다.");
    }
}

위의 예제 코드는 5x5 크기의 미로를 입력으로 받아, 출발점에서 도착점까지의 경로를 탐색하는 알고리즘을 구현한 것입니다. 미로는 0과 1로 구성되어 있으며, 0은 이동 가능한 경로를 나타내고, 1은 벽을 나타냅니다. 경로 탐색 결과에 따라 결과 메시지가 출력됩니다.

이렇게 스택을 사용하여 미로 찾기 알고리즘을 구현할 수 있습니다.

3. 결론

스택을 활용하여 깊이 우선 탐색 기반의 미로 찾기 알고리즘을 구현하는 방법을 알아보았습니다. 이를 활용하여 다양한 미로 문제를 해결할 수 있습니다. 만약 다른 알고리즘을 사용하여 미로를 탐색하고 싶다면 BFS 등의 다른 탐색 방식을 적용해보세요.

1. 스택(Stack) 이란?

2. 미로 찾기 알고리즘

3. 결론

참고 자료