Java 알고리즘 DFS 미로 탐색

 

오늘은 DFS를 활용한 미로 탐색 문제를 풀어보려고 합니다😄

DFS 미로탐색

 

개요

문제 내용

 

이 문제의 핵심은 DFS 알고리즘 활용과 상하좌우 4방향으로 이동하는 방법이 주가 될 것 같아요. 한번 코드로 풀어볼까요?

 

📌 사전 지식으로 DFS의 원리와 Stack이 쌓이고 pop 되는 과정을 알아야 합니다. 모르시는 분은 해당 링크를 클릭해서 확인해주세요😀

 

Setting📙

public class MazeSearch {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0 ,1, 0, -1};
    static int[][] board;
    static int result = 0;

    public static void main(String[] args) {
        MazeSearch T = new MazeSearch();
        Scanner sc = new Scanner(System.in);
        board = new int[8][8];
        for(int i = 1; i <= 7; ++i) {
            for(int j = 1; j <= 7; ++j) {
                board[i][j] = sc.nextInt();
            }
        }
        board[1][1] = 1;
        T.DFS(1,1);
        System.out.print(result);
    }
}

 

static으로 선언된 dx, dy는 각각 격자판에서 세로, 가로축을 의미하며 상하좌우 4방향으로 이동이 가능한지에 대해 조건문을 걸 때 사용됩니다. 자세한 설명은 DFS 함수에서 설명할게요

 

이중배열인 board는 말 그대로 입력받는 격자판에 해당하고, result는 미로를 탐색할 수 있는 총개수를 의미합니다.

 

main에서는 Scanner를 이용하여 격자판을 생성합니다. 7*7 격자판이지만 배열은 0부터 시작하기 때문에 사이즈를 8로 선언하고 1부터 차례대로 넣었습니다. 그리고 1,1 즉 출발지점은 1로 선언하였습니다. 이후에 다시 설명하겠지만 한번 지나간 통로는 1로 선언하여서 다시 지나갈 수 없게 조정해야 하기 때문입니다.

 

이후에 재귀함수인 DFS 함수를 실행시킵니다. 처음 시작은 1,1에서 시작하기 때문에 인자값으로 1,1을 넣었습니다.

 

DFS📘

public void DFS(int x, int y) {
    if(x == 7 && y == 7) {
        result++;
    } else {
        for(int i = 0; i < 4; ++i) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7
                    && board[nx][ny] == 0) {
                board[nx][ny] = 1;
                DFS(nx, ny);
                board[nx][ny] = 0;
            }
        }
    }
}

 

DFS 알고리즘은 대게 if~else문을 통해 구현됩니다. if 문에는 도착지점에 도착했을 경우를 의미하고 else문은 도착지점까지 재귀적으로 DFS를 뻗어나간다고 생각하시면 편할 것 같아요.

 

if문의 조건으로는 x축, y축 모두 7일 경우가 해당됩니다. 또한, 도착했다는 조건이기 때문에 탐색하는 방법의 개수인 result를 증가시켜 주면 됩니다.

 

else문에서는 반복문을 통해 상하좌우 4방향을 탐색해야 합니다. nx(next x)는 인자값으로 넘어온 x값에 이전에 static으로 선언한 dx[i] 값을 더해줍니다. ny(next y) 또한 인자값으로 넘어온 y값에 이전에 static으로 선언한 dy[i] 값을 더해줍니다.

 

즉 12시 방향부터 순차적으로 3시 방향, 6시 방향, 9시 방향을 가리킨다고 보시면 되는데, 맨 처음 1,1로 넘어왔을 때 x는 1, y는 1인 상태입니다. 그렇다면 int nx = 1 + (dx[i] = -1) : 0, int ny = 1 + (dy[i] = 0) : 1 -> (0, 1)을 뜻합니다. 즉 12시 방향인 것입니다. 

 

그다음 9시 방향 또한 반복문을 통해 int nx = 1 + (dx[i] = 0) : 1, int ny = 1 + (dy[i] = 1) : 2, 즉 (1,2)를 뜻합니다. 이런 식으로 상하좌우 4방향을 모두 탐색합니다.

---

if문에서는 nx와 ny가 1 이상 7 이하로 설정하였습니다. 이 부분은 격자판 테두리에 위치한 격자들이 격자판 밖으로 이동하지 않게 하기 위함입니다. 아까 예시처럼 1,1로 들어왔을 때 12시 방향은 nx가 0이 됩니다. 즉 격자판 밖은 쳐다보지 않겠다는 의미입니다.

 

또한 board[nx][ny] 즉, 다음 지점의 격자가 0이어야 합니다. 문제 설명을 보면 1은 벽을 뜻하고, 0은 통로를 뜻하기 때문입니다. 

 

마지막으로 격자를 밟았을 때는 1로 세팅해 주어서 걸어온 방향으로 다시 못 돌아가게 해 주고, 도착지점에서 나올 때는 0으로 초기화시켜서 다른 탐색 방법에서도 사용할 수 있게 해주어야 합니다. 이 부분은 글로 표현하기 힘들어서 직접 개요에 있는 격자판에서 시뮬레이션을 많이 돌려봐야 이해가 갈 것 같아요😅

 

Result📒

출력값

격자판을 입력하니 모든 미로의 개수인 8을 출력하는 것을 확인할 수 있었습니다.

 

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

마치며

지금까지 DFS 알고리즘을 활용해서 미로 탐색 문제를 풀어보았습니다. 다음 포스팅은 BFS를 활용한 미로의 최단 거리 통로를 구해보는 문제를 풀어볼 것 같네요😊