[백준] 2178번 : 미로 탐색

미로 탐색

---

풀이 방법

대표적인 BFS문제 미로 탐색 문제였다.
dx, dy를 통해서 좌표 접근을 하고, BFS로 최단 거리를 탐색하면 된다.

살짝 막혔던 부분이 있었는데,
최단 거리를 어떻게 계산할까 되게 복잡하게 생각하고 있었다.

근데 풀이 방법은 간단하게 다음 이동 경로에 기존의 값에 1씩을 더해주면 되는 간단한 문제였다.
그렇게 하면 최단 거리가 아닌 길을 들르더라도 결국 마지막 n,m에서 최단 거리를 구할 수 있게 된다.

알게된 점

큐 구현시 ArrayDeque , LinkedList의 차이

참고 블로그
https://velog.io/@newdana01/Java-%ED%81%90-%EA%B5%AC%ED%98%84%EC%8B%9C-ArrayDeque%EC%99%80-LinkedList-%EC%84%B1%EB%8A%A5-%EC%B0%A8%EC%9D%B4-Deque-Queue-%EC%9D%B8%ED%84%B0%ED%8E%98%EC%9D%B4%EC%8A%A4

ArrayDeque는 Queue의 서브인터페이스인 Deque의 구현체이고, LinkedList는 List와 Queue의 구현체이다. 그래서 LinkedList는 List의 특징, ArrayDeque는 배열의 특징을 가지고 있다.

연산 성능

ArrayDeque는 배열의 측면으로 삽입/삭제 연산의 시간 복잡도가 $O(1)$이므로 성능이 우수하다. 또한 Random access가 가능하기에 조회 시에도 속도가 빠르다.

LinkedList도 삽입/삭제 연산 성능이 좋지만, 특정 원소에 접근 시는 ArrayDeque에 비해 떨어진다.

메모리

ArrayDeque은 LinkedList와 달리 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용한다.

기타

• ArrayDeque은 크기 조정이 가능하다.
• ArrayDeque은 null을 요소로 추가할 수 없지만 LinkedList는 null을 추가할 수 없다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[][] map;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static boolean[][] visited;
    static int n,m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n+1][m+1];
        visited = new boolean[n+1][m+1];

        for(int i=1;i<=n;i++){
            String str = br.readLine();
            for(int j=1;j<=m;j++){
                map[i][j] = Integer.parseInt(String.valueOf(str.charAt(j-1)));
            }
        }

        bfs(1,1);
        System.out.println(map[n][m]);
    }

    private static void bfs(int x, int y) {
       Queue<int[]> queue = new ArrayDeque<>();
       queue.add(new int[] {x,y});
       visited[x][y] = true;

       while(!queue.isEmpty()) {
           int[] q = queue.remove();
           int nx = q[0];
           int ny = q[1];

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

               if (mx > 0 && my > 0 && mx <= n && my <= m) {
                   if (!visited[mx][my] && map[mx][my] != 0) {
                       queue.add(new int[]{mx, my});
                       visited[mx][my] = true;
                       
                       //다음 값에 이전 값의 1을 더해줘서 최단거리 계산
                       map[mx][my] = map[nx][ny] + 1;
                   }
               }
           }
       }
    }
}