미로의 최단거리 통로(BFS)

설명

7*7 격자판 미로를 탈출하는 최단경로의 길이를 출력하는 프로그램을 작성하세요.

경로의 길이는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다.

출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다.

격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위와 같은 경로가 최단 경로의 길이는 12이다.

 

입력

첫 번째 줄부터 7*7 격자의 정보가 주어집니다.

 

출력

첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.

 

예시 입력 1 

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0

 

예시 출력 1

12

 

 

문제 해결

 

미로에서 최단 경로를 찾는 문제로 BFS로 해결할 수 있따.

static int[][] maze;
static int[] dx = {-1, 1 ,0 ,0}; //x좌표 이동
static int[] dy = {0, 0, -1, 1}; //y좌표 이동
static boolean[][] visited;

• 7x7 격자판 미로는 2차원 배열이므로 2차원 배열을 저장할 수 있는 maze 배열을 선언한다.
• 상하좌우로 이동하는 이동 방향을 나타내는 배열인 dx, dy도 선언해준다.
• 방문여부를 저장할 visited 배열이다. 격자판 위의 위치를 나타내므로 이또한 2차원 배열로 선언해준다!

 

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    maze = new int[7][7];
    visited = new boolean[7][7];

    for(int i = 0; i < 7; i++) {
        for(int j = 0; j < 7; j++) {
            maze[i][j] = in.nextInt();
        }
    }

    int result = BFS(0,0);
    System.out.println(result);
}

• 7x7 격자판 숫자들을 입력받아준 후 maze 배열에 각 위치의 값을 저장한다.
• 시작 좌표로 BFS 메서드를 호출하고 결과를 출력한다.

 

public static int BFS(int startX, int startY ){
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(startX*7+startY);
    queue.offer(0);
    visited[startX][startY] = true;

• 시작 위치를 (startX * 7 + startY)로 큐에 추가해 정수로 저장한다. ==>  (x, y) 좌표를 하나의 정수로 저장
• 시작 거리인 0을 큐에 추가하고 시작 위치를 방문처리한다.

 

while (!queue.isEmpty()) {
    int pos = queue.poll();
    int distance = queue.poll();
    int x = pos / 7;
    int y = pos % 7;

• 큐에서 현재 위치와 거리 꺼내기
  • queue.poll()을 두 번 호출하여 큐에서 값을 꺼낸다.
    • 첫 번째로 꺼낸 값은 현재 위치를 나타내는 pos이고,
    • 두 번째로 꺼낸 값은 현재 위치까지의 거리 distance이다.
  • pos는 하나의 정수로 저장된 (x, y) 좌표이므로. 이를  x와 y 좌표로 변환해줘야 한다.:
    • x = pos / 7: pos를 7로 나눈 몫이 x 좌표
    • y = pos % 7: pos를 7로 나눈 나머지가 y 좌표

 

if (x == 6 && y == 6) {
    return distance;
}

• 현재 위치가 도착점인지 확인
  • 현재 위치가 도착점 (6, 6)인지 확인하고
  • 만약 도착점이라면, 현재까지의 거리 distance를 반환한다. (==> 최단거리)

 

for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 격자판 범위 내에 있고, 방문하지 않았고, 벽이 아닌 경우
            if (nx >= 0 && nx < 7 && ny >= 0 && ny < 7 && !visited[nx][ny] && maze[nx][ny] == 0) {
                visited[nx][ny] = true;
                queue.offer(nx * 7 + ny); // 새로운 위치 저장
                queue.offer(distance + 1); // 현재 거리 + 1
            }
        }
    }
    return -1;
}

• 상하좌우 네 방향으로 이동할 수 있으므로 다음과 같이 for문으로 돌며 새로운 x좌표와 y좌표를 계산해준다.
  
  • 미로 범위를 벗어나지 않았고 방문하지 않았고, 벽이 아닌 위치라면
  • 방문 표시를 하고 새로운 위치와 거리를 큐에 추가해준다..
• 큐가 비어있고 도착점에 도달하지 못한 경우, -1을 반환한다.

 

최종 코드

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class P11_미로의최단거리통로_BFS {
    static int[][] maze;
    static int[] dx = {-1, 1 ,0 ,0}; //x좌표 이동
    static int[] dy = {0, 0, -1, 1}; //y좌표 이동
    static boolean[][] visited;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        maze = new int[7][7];
        visited = new boolean[7][7];

        for(int i = 0; i < 7; i++) {
            for(int j = 0; j < 7; j++) {
                maze[i][j] = in.nextInt();
            }
        }

        int result = BFS(0,0);
        System.out.println(result);
    }

    public static int BFS(int startX, int startY ){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(startX*7+startY);
        queue.offer(0);
        visited[startX][startY] = true;

        while (!queue.isEmpty()) {
            int pos = queue.poll();
            int distance = queue.poll();
            int x = pos / 7;
            int y = pos % 7;


            if (x == 6 && y == 6) {
                return distance;
            }

            // 상하좌우 이동
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 격자판 범위 내에 있고, 방문하지 않았고, 벽이 아닌 경우
                if (nx >= 0 && nx < 7 && ny >= 0 && ny < 7 && !visited[nx][ny] && maze[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    queue.offer(nx * 7 + ny); // 새로운 위치 저장
                    queue.offer(distance + 1); // 현재 거리 + 1
                }
            }
        }
        return -1;
    }
}