Baekjoon | Q.2178 - 미로 탐색

2178번: 미로 탐색

 N x M 행렬로 주어진 미로를 탐색하는 문제이다. (1, 1)에서 출발하여 (N, M)까지 도달하는데 필요한 최소 칸 수를 찾아내야 한다.

 

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

class Main {
  static int[][] maze;  // 미로
  static boolean visit[][]; // 방문 여부 체크

  static int[] dx = {-1, 0, 1, 0};  // 시계방향으로 연결 여부 체크할 예정
  static int[] dy = {0, 1, 0, -1};

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    maze = new int[n][m];
    visit = new boolean[n][m];

    for (int i = 0; i < n; i++) {
      String mazeStr = sc.next();
      for (int j = 0; j < m; j++) {
        // 입력된 정보를 미로에 저장하자
        maze[i][j] = Integer.parseInt(mazeStr.charAt(j) + "");
      }
    }
    sc.close();

    bfs();

    System.out.println(maze[n-1][m-1]);

  }

  static void bfs() {
    Queue<Integer> qx = new ArrayDeque<>(); // x좌표 정보를 담을 큐
    Queue<Integer> qy = new ArrayDeque<>(); // y좌표 정보를 담을 큐
    qx.add(0);  // start
    qy.add(0);
    visit[0][0] = true;

    while(!qx.isEmpty() && !qy.isEmpty()) { // 더 이상 인접한 좌표가 없을 때까지(큐가 빌 때 까지)
      int x_now = qx.poll();
      int y_now = qy.poll();

      for (int i = 0; i < dx.length; i++) { // 시계방향으로 인접한 좌표를 탐색
        int x_next = x_now + dx[i];
        int y_next = y_now + dy[i];

        if(x_next >= 0 && y_next >= 0
            && x_next < maze.length && y_next < maze[0].length) { // ArrayIndexOutOfBoundsException 방지
          if(maze[x_next][y_next] == 1 && !visit[x_next][y_next]) { // 미로가 연결되어 있으며 방문한 적 없을 경우
            qx.add(x_next); // 좌표를 큐에 추가
            qy.add(y_next);
            visit[x_next][y_next] = true; // 방문 여부 추가
            maze[x_next][y_next] = maze[x_now][y_now] + 1;  // 이동 횟수를 갱신
          }
        }
      }
    }
  }
}

 

 처음에 미로를 탐색할 때 상, 하, 좌, 우를 모두 탐색해야 하는데 어떠한 방식으로 해야할 지 어려움을 겪었다.... dx[], dy[] 두 배열을 이용하여 x 이동, y 이동을 4가지 방면으로 설정해주는 것으로 해결했다.

 그리고 이동 횟수를 전역 변수로 선언하여 이동할 때 마다 +1 해주면 된다고 생각했는데 그러면 모든 경로가 전부 카운팅되어 잘못된 답이 나왔다..... 이동 횟수를 좌표에 저장하는 것으로 해결했다.