[백준2178] 미로 탐색

[백준2178] 미로 탐색

제한조건

시간 : 1초
메모리 : 192M

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.
다음 N개의 줄에 M개열의 정수 미로가 주어진다.

출력

지나야 하는 최소의 칸 수. 시작 칸을 1 부터 셈한다.

자료구조

• Array

  
  static int[] dx = { 0, 0, 1, -1 };
  static int[] dy = { 1, -1, 0, 0 };
  static int[][] map;
  static int[][] cost;
  static boolean[][] visited;
  static int N, M, i, j, steps;
  
  static class Cell {
      int x;
      int y;
      int c;
  
      Cell(int x, int y, int c) {
          this.x = x;
          this.y = y;
          this.c = c;
      }
  }

• Queue

  
  Deque<Cell> q = new ArrayDeque<Cell>();

알고리즘

• BFS

  
  static void bfs(int x, int y, int c) {
      int curX, curY, curC, nextX, nextY, nextC;
      Deque<Cell> q = new ArrayDeque<Cell>();
      q.add(new Cell(x, y, c));
      visited[x][y] = true;
      while (!q.isEmpty()) {
          Cell cur = q.poll();
          curX = cur.x;
          curY = cur.y;
          curC = cur.c;
          for (i = 0; i < 4; i++) {
              nextX = curX + dx[i];
              nextY = curY + dy[i];
              nextC = curC + 1;
              if (!OOB(nextX, nextY)) {
                  if (map[nextX][nextY] == 1 && !visited[nextX][nextY]) {
                      q.add(new Cell(nextX, nextY, nextC));
                      visited[nextX][nextY] = true;
                      cost[nextX][nextY] = nextC;
                  }
              }
          }
      }
  }

풀이(java)

github#1

markdown syntax

markdown syntax