백준 2178 미로 탐색(Java)

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

2178번: 미로 탐색

---

 

해석 및 팁

 

---

 

이 문제는 bfs를 활용하면 되는 문제입니다. 다만 방문하는지 점을 이전지점 +1 을해주면 몇 번째에 방문했는지 알 수 있기 때문에 쉽게 풀 수 있습니다.

---

 

Java 코드

 

---

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

public class Main {
  
  static int n, m;
  static int[][] arr;
  static boolean[][] visit;
  static int[] dx = {1, -1, 0, 0};
  static int[] dy = {0, 0, -1, 1};

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();
    m = sc.nextInt();

    arr = new int[n][m];
    visit = new boolean[n][m];

    for(int i = 0; i < n; i++) {
      String s = sc.next();
      for(int j = 0; j < m; j++) arr[i][j] = s.charAt(j) - '0';
    }

    bfs(0, 0);

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

  public static void bfs(int a, int b) {
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[] {a, b});
    visit[a][b] = true;
    while(!q.isEmpty()) {
      int num[] = q.poll();
      
      for(int i = 0; i < 4; i++) {
        int x = num[0] + dx[i];
        int y = num[1] + dy[i];
        if(x >=0 && x < n && y >= 0 && y < m && arr[x][y] != 0 && visit[x][y] == false) {
          visit[x][y] = true;
          q.add(new int[] {x, y});
          arr[x][y] = arr[num[0]][num[1]] + 1;
        }
      }
    }
    
  }
}