[BOJ] 2178번 미로 탐색 java 풀이

https://www.acmicpc.net/problem/2178

package acmicpc;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

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

public class BJ_2178 {
  static int[] dx = {1, -1, 0, 0};
  static int[] dy = {0, 0, 1, -1};
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] s = br.readLine().split(" ");
    int n = Integer.parseInt(s[0]);
    int m = Integer.parseInt(s[1]);
    int[][] a = new int[n][m];
    boolean[][] visited = new boolean[n][m];
    int[][] count = new int[n][m];

    for (int i = 0; i < n; i++) {
      String s2 = br.readLine();
      for (int j = 0; j < m; j++) {
        a[i][j] = s2.charAt(j) - '0';
      }
    }
    Queue<Pos> q = new LinkedList<>();
    q.add(new Pos(0, 0)); // 출발지
    visited[0][0] = true;
    while (!q.isEmpty()) {
      Pos p = q.remove();
      int x = p.x;
      int y = p.y;
      for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (0 <= nx && nx < n && 0 <= ny && ny < m) { // 행, 열(0,1)(0,-1)(1,0)(-1,0) 이동
          if (!visited[nx][ny] && a[nx][ny] == 1) { // 방문 안했던 길인 경우
            q.add(new Pos(nx, ny));
            count[nx][ny] = count[x][y] + 1;
            visited[nx][ny] = true;
          }
        }
      }
    }

    System.out.println(count[n-1][m-1] + 1);
  }
}

• 이 문제를 DFS로 풀다가 막혔었다. 왜냐면 DFS로 풀게 되면 가지 않아도 될 경로까지 꼼꼼하게 탐색을 하기 때문이다.
• 그래서 이 문제는 갈림길이 나올때마다 내 분신을 만들어서 한걸음씩 걷다가 출구에 도착하면 그 사람이 걸은 만큼을 계산할 수 있는 BFS로 푸는게 정답이였다.
• 이런 미로나 체스판 문제에서 상위권 런타임시간을 가진 사람들의 풀이를 보니 dx, dy같은 좌표배열을 만들어놓고 for문을 이용해서 편하게 상하좌우 이동 좌표를 만드는게 신기해보여서 나도 한번 베껴봤다. 만약에 8방향 이동이 가능하다면 그 배열길이도 8이 되고 dx,dy를 0,-1,1의 조합으로 만들면 될것이다.