[자바] Swing과 DFS로 미로 생성기 만들기

 

https://uknowblog.tistory.com/364

[알고리즘] 그래프 탐색 - 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)

 

 

위 DFS/BFS 글을 쓰기 위해 자료조사를 하고 있을 때 였습니다.

DFS의 예시로 좋은게 뭐가 있을까 찾던 중에 한 충격적인 영상을 보게 되었습니다.

 

https://www.youtube.com/watch?v=0kaHIfrB3T4&ab_channel=DaveStephens 

 

 

DFS를 사용한 미로 생성 (찾기가 아닌 미로 생성) 영상을 보고 저는 충격에 빠졌고,

이걸 당장 해보고 싶었으나... 당면한 일이 너무 많아 지금에서야 구현을 해보게 되었습니다.

 

콘솔창에 문자열 형태로 찍는 것도 좋지만, 미로를 생성해나가는 모습을 보여주고 싶었기에,

어느정도 익숙한 Swing을 써서 구현을 해보기로 했습니다.

 

 

컨테이너

 

 

 

먼저, 컨테이너와 각 미로의 칸을 생성하는 부분입니다.

전체의 컨테이너를 하나 두고, 안에 row * col 개의 패널을 넣고,

각각의 패널을 색칠하는 방식으로 구현할 예정입니다.

 

 

 

DFS를 통해 미로 만들기

원리?

 

DFS를 통해 매번 상하좌우 중 랜덤한 방향으로 탐색을 할 것입니다.

 

 

 

 

매 번 랜덤한 방향으로 탐색하다가, 통로(이미 탐색한 부분)를 만난다면 직전의 길로 돌아가 

다른 방향으로 탐색을 진행합니다.

 

 

 

 

이전 길에서 더 이상 찾을 길이 없다면 다시 이전 노드로, 또 다시 찾을 게 없다면 이전 노드로,

DFS의 원리를 그대로 사용하여 모든 길을 다 탐색할 때 까지 모든 경로를 방문하는 것입니다.

 

 

 

DFS 소스코드

private void dfs(int x, int y) {
        maze[x][y] = true;
        shuffleArray(directions);

        for (int[] direction : directions) {

            /*
                nx, ny를 1칸 바로 옆의 칸으로 설정하면 미로의 벽이 없어짐
                nx, ny를 2칸 다음의 칸으로 설정하여 벽이 없어지는 것을 방지
             */

            int nx = x + direction[0] * 2;
            int ny = y + direction[1] * 2;

            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && !maze[nx][ny]) {
                maze[nx][ny] = true;
                maze[x + direction[0]][y + direction[1]] = true;

                try {
                    Thread.sleep(1); // 미로가 생성되는 속도를 조절
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                // 2칸 떨어진 다음 칸과 그 사이 칸을 칠함
                paintCellAndRefresh(nx, ny, Color.WHITE);
                paintCellAndRefresh(x + direction[0], y + direction[1], Color.WHITE);

                dfs(nx, ny);
            }
        }

 

 

원리 자체는 일반적인 DFS와 동일하나,

주의할 점은 바로 옆의 칸을 다음 칸으로 지정하는 것이 아닌 2칸만큼 떨어진 칸을 다음 칸으로 탐색하는 것입니다.

 

 

바로 옆의 다음 칸으로 지정할 경우, 위와 같이 통로와 통로가 서로 합쳐지는 경우가 생기기 때문입니다.

 

 

 

때문에 이를 방지하기 위해서는, 길과 길 사이에 1칸의 벽이 항상 있어야 합니다.

 

때문에 2칸이 떨어진 칸을 다음 칸으로 지정하고, 해당 칸을 방문하지 않았다면,

해당 칸과 그 사이에 있는 칸을 방문처리 및 하얀색으로 칠해야 합니다.

 

위와 같은 방법으로 통로가 서로 이어지지 않게 하면서 미로를 생성할 수 있게 됩니다.

 

 

전체 소스코드

import javax.swing.*;
import java.awt.*;

public class MazeGenerator extends JFrame {
    private final Container container = getContentPane();
    private final JPanel[][] cells;
    private final int rows;
    private final int cols;
    private final boolean[][] maze;
    private final int[][] directions = {
            {1, 0},  // Down
            {0, 1},  // Right
            {-1, 0}, // Up
            {0, -1}  // Left
    };

    public MazeGenerator(int rows, int cols, int cellSize) {
        this.rows = rows;
        this.cols = cols;
        this.maze = new boolean[rows][cols];
        this.cells = new JPanel[rows][cols];

        setTitle("Maze Generator");
        setSize(cols * cellSize, rows * cellSize);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setLocationRelativeTo(null);
        setVisible(true);

        init();
        generateMaze();
    }

    private void init() {
        container.setLayout(new GridLayout(rows, cols));
        container.setBackground(Color.BLACK);

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                cells[row][col] = new JPanel();
                container.add(cells[row][col]);
                cells[row][col].setBackground(Color.BLACK);
            }
        }

        container.revalidate();
        container.repaint();
    }

    private void paintCellAndRefresh(int row, int col, Color color) {
        cells[row][col].setBackground(color);
        container.revalidate();
        container.repaint();
    }

    private void generateMaze() {
        paintCellAndRefresh(0, 0, Color.RED); // 시작점 표시 (빨간색)
        dfs(0, 0); // DFS 알고리즘으로 미로 생성
        paintCellAndRefresh(rows - 2, cols - 2, Color.GREEN); // 도착점 표시 (초록색)
    }

    private void dfs(int x, int y) {
        maze[x][y] = true;
        shuffleArray(directions);

        for (int[] direction : directions) {

            /*
                nx, ny를 1칸 바로 옆의 칸으로 설정하면 미로의 벽이 없어짐
                nx, ny를 2칸 다음의 칸으로 설정하여 벽이 없어지는 것을 방지
             */

            int nx = x + direction[0] * 2;
            int ny = y + direction[1] * 2;

            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && !maze[nx][ny]) {
                maze[nx][ny] = true;
                maze[x + direction[0]][y + direction[1]] = true;

                try {
                    Thread.sleep(1); // 미로가 생성되는 속도를 조절
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                // 2칸 떨어진 다음 칸과 그 사이 칸을 칠함
                paintCellAndRefresh(nx, ny, Color.WHITE);
                paintCellAndRefresh(x + direction[0], y + direction[1], Color.WHITE);

                dfs(nx, ny);
            }
        }
    }

    // 방향 배열을 랜덤하게 섞음
    private void shuffleArray(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            int j = (int) (Math.random() * (i + 1));
            int[] temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 화면 크기 조절 시 화면을 다시 그림
    @Override
    public void paint(Graphics g) {
        super.paint(g);
    }

    public static void main(String[] args) {
        new MazeGenerator(100, 180, 10);
    }
}

 

 

 

 

전체 소스코드는 아래 깃허브에서도 볼 수 있습니다.

https://github.com/yoon6763/maze-generator

GitHub - yoon6763/maze-generator: DFS를 통한 미로 생성기

 

 

 

 

실행화면

(동영상)

 

(GIF)

 

 

 

후기

DFS 포스팅을 위해 자료조사를 하던 중,

DFS로 미로찾기를 만드는 것을 보고 홀린듯이 직접 만들어보고 싶어졌고,

꽤 쉽고 간단하게 GUI를 그릴 수 있는 Swing으로 만들어봤습니다.

 

미로의 경로가 계속 합쳐지는 바람에 꽤나 애먹던 중,

2칸 떨어진 곳의 칸을 체크하여 해당 칸과 현재의 칸 사이의 칸을 이어주는 방식으로 구현하여 해결했습니다.

덕분에 꽤 만족스러운 결과가 나왔네요.

 

 

 

 

 

 

이왕 만들어본 김에 그림판으로 미로찾기를 해봤습니다. 동심으로 돌아간 느낌이네요.

언젠가 DFS로 미로를 만든 뒤, BFS로 찾는 프로그램으로 돌아오겠습니다.