Java 알고리즘 BFS 미로 최단 경로 구하기

오늘은 BFS를 활용하여 미로의 최단 경로를 구해보는 문제를 풀어볼 예정입니다. 이전 포스팅에서 풀어 본 DFS를 활용한 미로 탐색과 풀이법이 유사하기 때문에 참고하면 좋을 듯하네요😊

 

DFS 부분집합

 

개요

문제 내용

 

이 문제의 핵심은 BFS 알고리즘 활용과 Queue의 원리, 지나간 경로는 다시금 못 지나가게 막는 방법, 격자의 상하좌우 확인 총 4가지가 될 것 같아요. 한번 코드로 풀어볼까요?

 

Point📙

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

Point 클래스는 격자판에서 x축, y축을 입력할 때 사용합니다. Queue에 지나간 격자를 넣거나 빼서 사용할 때 Point 클래스를 사용하여 현재 위치를 파악할 때 사용합니다. 자세한 설명은 하단에서 하겠습니다😀

 

Setting📘

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

    public static void main(String[] args) {
        SearchMazeBFS T = new SearchMazeBFS();
        Scanner sc = new Scanner(System.in);
        board = new int[8][8];
        dis = new int[8][8];
        for(int i = 1; i <= 7; ++i) {
            for(int j = 1; j <= 7; ++j) {
                board[i][j] = sc.nextInt();
            }
        }
        T.BFS(1,1);
        if(dis[7][7] == 0) {
            System.out.println(-1);
        } else {
            System.out.println(dis[7][7]);
        }
    }
}

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

 

이중배열인 board는 말 그대로 입력받는 격자판에 해당하고, dis 이중배열은 각각의 격자가 출발점으로 얼만큼 떨어져 있는지에 대해 체크하는 배열입니다. 

 

main에서는 Scanner를 이용해서 격자판을 생성합니다. 7*7 격자판이지만 배열은 0부터 시작하기 때문에 사이즈를 8로 선언하고 1부터 차례대로 넣었습니다. 이후에 하단에서 만들 DFS 함수를 실행시키고 인자값으로는 시작점인 1,1을 넣었습니다.

 

DFS 함수가 종료되면 dis 이중배열에 최단 거리가 구해집니다. dis[7][7] 즉 도착점이 만약 0이라면 미로의 도착점까지 도달할 수 없다는 뜻이기 때문에 문제 내용처럼 -1을 출력하였습니다. 반대로 도착할 수 있다면 최단 거리인 dis[7][7]를 출력하였습니다.

 

BFS📒

public void BFS(int x, int y) {
    Queue<Point> Q = new LinkedList<>();
    Q.offer(new Point(x,y));
    board[x][y] = 1;
    while(!Q.isEmpty()) {
        Point tmp = Q.poll();
        for(int i = 0; i < 4; ++i) {
            int nx = tmp.x + dx[i];
            int ny = tmp.y + dy[i];
            if(nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7
                    && board[nx][ny] == 0){
                board[nx][ny] = 1;
                Q.offer(new Point(nx, ny));
                dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
            }
        }
    }
}

BFS 함수는 초기값으로 시작점인 1,1이 들어옵니다. Queue를 미리 만든 Point 클래스를 이용하여 선언하고, 시작점을 offer 함수를 이용하여 Q에 넣어줍니다.

 

그리고 시작점인 board[1][1]를 1로 세팅해 줍니다. 시작점을 1로 만들지 않고, 0으로 놔두면 격자판을 이용했다가 다시 돌아오는 경우를 막지 않기 때문에 꼭 세팅해주어야 합니다.

 

BFS는 Q가 비어있지 않을 때까지 돌아야 하기 때문에 지금까지 풀어온 것처럼 while문을 사용해야 합니다. while문 안에서 Q에서 값을 하나 꺼내고, 그 값(현재 격자판 위치)에서 상하좌우 4방향으로 이동하는 구조입니다.

 

현재 위치(tmp)에서 미리 선언한 dx와 dy를 이용하여 상하좌우를 확인하는데, 예시로 맨 처음 시작점 tmp는 (1,1)이고, int nx = tmp.x (= 1) + dx[i] (= -1) : 0, int ny = tmp.y (= 1) + dy[i] (= 0) : 1이기 때문에 (0,1)를 바라봅니다.

 

하지만 현재 격자의 12시 방향인 (0,1)은 격자판 밖에 위치하기 때문에 이동해서는 안됩니다. 이렇게 반복문 4번을 돌면서 12시 방향, 3시 방향, 6시 방향, 9시 방향을 확인한다고 생각하시면 되고 그 로직이 if 조건문입니다. 당연히 격자판의 시작인 1 이상이어야 하고, 마지막인 7 이하이어야 합니다.

 

또한, 문제 내용 상 벽에 해당하는 1은 격자가 이동하면 안 되기 때문에 board[nx][ny]가 0일 때만 이동해야 합니다. 마지막으로 지나간 격자는 1로 세팅해서 다시금 그 격자를 못 지나가게 막아주어야 합니다.

---

if 조건문을 통과했다는 얘기는 격자가 이동했다는 얘기와 동일합니다. 그렇기 때문에 이동한 격자인 board[nx][ny]를 1로 세팅해 주고, Q에 쌓아줍니다.

 

그리고 지금까지 이동해 온 격자의 수를 담는 이중배열 dis도 세팅을 해주어야 합니다. 예시로, 첫 시작점인 (1,1)인 상태에서 미로상 밑으로 내려간다고 가정했을 때, 다음 격자판 dis[1][0]는 (dis[tmp.x = 1][tmp.y = 1] = 0) + 1 수식이 들어가서 dis[1][0] = 1 즉, 1번 이동했다고 표시해주어야 합니다.

 

📌 그다음은 2, 3, 4... 격자판의 0을 만날 때마다 dis 좌표는 이전 값에서 +1 되어 증가되는 구조입니다.

 

BFS는 넓이 우선 탐색이기 때문에 미로 탐색의 모든 경우의 수를 동시에 진행한다고 생각하셔도 됩니다. 문제 상으로는 시작점에서 오른쪽으로 가는 방법과, 밑으로 내려가는 방법이 있는대 두 명의 사람이 동시에 출발하는 느낌으로 코드가 진행됩니다.

 

여기서 먼저 도착하는 사람이 있겠죠? 그럼 그 사람이 1이라는 깃발을 도착점에 꽃는다고 생각하시면 됩니다. 그럼 그다음 사람은 도착점이 1이기 때문에 도착하지 못하고 결국엔, dis 이중 배열의 도착점인 dis[7][7]에는 가장 먼저 도착한 사람이 밟아 온 격자 개수만 남게 됩니다.

 

Result📗

결과

격자판을 입력하니 미로의 최단 경로인 12를 출력하는 것을 확인할 수 있었습니다.

 

 

---

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

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

 

참여코드 : 456456

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

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

 

---

👨‍💻 전자책 출간

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

https://kmong.com/gig/480954

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

---

 

마치며

지금까지 BFS를 활용해서 미로의 최단 경로를 구해보았습니다. DFS를 활용해 미로 탐색 문제와 비슷한 부분이 많지만 원리 자체가 다르기 때문에 헷갈리는 부분도 많았네요. 다음 문제도 BFS 관련 문제를 풀어볼게요😄