[백준] 2178 미로 탐색(JAVA)

💡 문제 

---

N×M크기의 배열로 표현되는 미로가 있다.

 

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

 

 

해결 방법:

이 문제는 DFS와 BFS 알고리즘을 이용해서 풀 수 있다. DFS 알고리즘은 최단거리를 찾으려면 완전 탐색을 하고 그중에서 가장 작은 값을 선택해야 하는데 경로가 아주 많을 수 있으므로 시간 복잡도가 매우 커진다. 반면 BFS는 최단거리를 보장하기 때문에 이러한 문제들 (최단거리 구하기)은 BFS로 푸는 것이 좋다.

 

이 문제를 풀기 위해서는 미로의 각 칸을 정점으로 생각하고 각 칸 사이의 연결관계를 그래프로 나타내야 한다. 그 다음 BFS 알고리즘을 이용해서 시작점에서부터 도착점까지의 최단거리를 구하면 된다.

먼저 미로의 정보를 입력받아서 2차원 배열에 저장한다. BFS를 실행하면서 현재까지 이동한 칸 수를 저장한다. 시작점에서부터 BFS를 실행하면서 도착점에 도달할 때까지 이동한 칸 수를 저장하면 되는데, 이 때 도착점에 도달했을 때의 이동한 칸 수가 최소값이 된다.

 

 

알고리즘:

BFS

 

시간복잡도:

O(NM)

 

 

코드 실행 순서:

1. 입력값으로 받은 미로를 2차원 배열로 저장
2. 시작점 (0, 0)에서 BFS 알고리즘을 시작
3. 큐에 시작점을 넣고 방문했음을 표시
4. 큐가 빌 때까지 다음을 반복
   1. 큐에서 정점을 하나 꺼낸다.
   2. 꺼낸 정점에서 갈 수 있는 모든 정점을 큐에 넣고 방문했음을 표시
   3. 이때, 각 정점까지의 거리를 이전 정점까지의 거리 + 1로 계산
5. 도착점 (n-1, m-1)까지의 최단거리 출력

 

 

💭 리뷰

미로를 2차원 배열로 받아서 각 칸을 정점으로 생각하고 각 칸 사이의 연결관계를 그래프로 나타내려고 노력했다. 그 다음 BFS 알고리즘을 이용해서 시작점에서부터 도착점까지의 최단거리를 구하는 게 시간이 걸렸다.

 

 

- offer()

Queue 인터페이스는 add(), offer(), poll() 같은 메소드를 제공하는데, add()대신 offer()을 사용했다.

add(E e) : 큐에 요소 추가, 큐가 가득 차 있는 경우 예외를 발생시킨다.
offer(E e) : 큐에 요소 추가, 큐가 가득 차 있는 경우 false를 반환한다.

poll() : 큐에서 요소를 제거하고 반환, 큐가 비어있는 경우 null을 반환

즉, add 메소드는 큐가 가득 차 있는 경우 예외를 발생시키지만, offer 메소드는 false를 반환한다. 따라서 큐가 가득 차 있는 경우 예외를 처리하는 것이 번거로울 때는 offer 메소드를 사용하는 것이 좋다고 판단해서 offer()를 사용했다.

- poll()

remove() 메소드는 큐의 head 요소를 제거하고 그 값을 반환한다. 그런데 큐가 비어있으면 NoSuchElementException 예외를 발생시킨다.

반면에 poll() 메소드는 큐의 head 요소를 제거하고 그 값을 반환한다. 큐가 비어있으면 null을 반환한다.

 

 

 

🖍 내 답안

---

import java.util.*;

public class boj2178 { // 미로 탐색 실버1
    static int n, m;
    static int[][] maze; // 미로의 정보를 저장하는 2차원 배열
    static boolean[][] visited; // 방문 여부를 저장하는 2차원 배열
    static int[] dx = {-1, 0, 1, 0}; // 상, 우, 하, 좌 순서로 이동하기 위한 배열
    static int[] dy = {0, 1, 0, -1};

    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>(); // BFS를 위한 큐
        q.offer(new int[]{x, y}); // 시작점을 큐에 추가
        visited[x][y] = true; // 시작점 방문 처리
        while (!q.isEmpty()) { // 큐가 비어있지 않은 동안 반복
            int[] point = q.poll(); // 큐에서 점 하나를 꺼내서
            for (int i = 0; i < 4; i++) { // 상, 우, 하, 좌 순서로 이동할 수 있는지 확인
                int nx = point[0] + dx[i]; // 이동한 위치의 x 좌표
                int ny = point[1] + dy[i]; // 이동한 위치의 y 좌표
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) { // 미로를 벗어난 경우
                    continue; // 다음 이동 방향 확인
                }
                if (maze[nx][ny] == 0) { // 이동할 수 없는 경우 (벽인 경우)
                    continue; // 다음 이동 방향 확인
                }
                if (!visited[nx][ny]) { // 방문하지 않은 경우
                    visited[nx][ny] = true; // 방문 처리
                    maze[nx][ny] = maze[point[0]][point[1]] + 1; // 현재까지 이동한 칸 수를 저장
                    q.offer(new int[]{nx, ny}); // 큐에 추가
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 미로의 세로 길이
        m = sc.nextInt(); // 미로의 가로 길이
        maze = new int[n][m]; // 미로 정보를 저장할 배열 초기화
        visited = new boolean[n][m]; // 방문 여부를 저장할 배열 초기화
        for (int i = 0; i < n; i++) { // 미로 정보 입력 받기
            String row = sc.next(); // 한 줄씩 입력 받음
            for (int j = 0; j < m; j++) { // 각 칸에 대해
                maze[i][j] = row.charAt(j) - '0'; // 문자열을 숫자로 변환하여 미로 배열에 저장
            }
        }
        bfs(0, 0); // 시작점 (0, 0)에서 BFS 시작
        System.out.println(maze[n - 1][m - 1]); // 도착
    }
}