미로 탐색

문제 풀러가기

2178

코드

  import java.io.*;
  import java.util.*;

  class node { // x y 좌표 저장 클래스
    int x;
    int y;

    public node(int x,int y) {
      this.x = x;
      this.y = y;
    }
  }

  public class Main {
	   static int map[][]; // 2차원 미로 배열
     static int check[][]; // 2차원 방문여부 배열
     static int cnt = 1; // 시작점을 포함하기 때문에 1로 초기화
	   static int n, m;

     public static void main(String[] args) throws Exception {
       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][m];
       check = new int[n][m];

       for(int i = 0; i < n; i++) { // 줄 단위 값을 저장
         String row = br.readLine();

         for(int j = 0; j < m; j++) {
           map[i][j] = row.charAt(j) - '0';
         }
       }
       bfs(1, 1); // 시작점 전달

       System.out.println(check[n - 1][m - 1]); // 방문배열의 마지막 원소 도착지점의 값을 반환
   	}

    public static void bfs(int a, int b) {
      Queue<node> queue = new LinkedList<>();
      a -= 1; // 시작점이 (1, 1)로 들어오므로 -1
      b -= 1;
      check[a][b] = cnt; // 방문배열에서 시작점 저장

      queue.offer(new node(a, b)); // 시작점 객체를 큐에 삽입

      while(!queue.isEmpty()) {
        int x = queue.peek().x; // 큐에 저장되어 있는 객체에서 x,y좌표를 저장
        int y = queue.peek().y;
        queue.poll(); // 해당 객체 소멸

        if(y < map[x].length - 1 && map[x][y] == 1
        && map[x][y + 1] == 1 && check[x][y + 1] == 0) {
          check[x][y + 1] = check[x][y] + 1; // 현재 경로값을 인접한 방문배열에 저장
          queue.offer(new node(x, y + 1)); // 인접한 점을 큐에 저장
        }

        if(x < map.length - 1 && map[x][y] == 1
        && map[x + 1][y] == 1 && check[x + 1][y] == 0) {
          check[x + 1][y] = check[x][y] + 1;
          queue.offer(new node(x + 1, y));
        }

        if(x > 0 && map[x][y] == 1 && map[x - 1][y] == 1 && check[x - 1][y] == 0) {
          check[x - 1][y] = check[x][y] + 1;		
          queue.offer(new node(x - 1, y));
        }

        if(y > 0 && map[x][y] == 1 && map[x][y - 1] ==1 && check[x][y - 1] == 0) {
          check[x][y - 1] = check[x][y] + 1;
          queue.offer(new node(x, y - 1));
        }
      }
    }
  }

설명