미로 탐색(BFS)

27 May 2023 in Algorithm on Java, Coding, Test

문제

설명

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요.

출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다.

격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

입력

7*7 격자판의 정보가 주어집니다.

출력

첫 번째 줄에 경로의 가지수를 출력한다.

예시 입력 1

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0

예시 출력 1

8

해결방법

• 상하좌우 움직이는 부분은 항상 갈 수 있는 좌표를 x,y로 구분하여 미리 1차원 배열로 각각 선언 해놓고 반복을 통해 해당 좌표를 참고한다.
• 상하좌우 찾아가는 부분은 반복문을 통해 구현하여 방문한다.

코드

import java.util.Scanner;

class Main {
  // 상,하,좌,우 구하는 배열 (순서대로 위치 값 계산)  
  static int[] dx = {-1, 0, 1, 0};
  static int[] dy = {0, 1, 0, -1};
  static int[][] board;
  static int answer = 0;

  public void DFS(int x, int y) {
    // 도착한 경우, 경우의 수 1증가  
    if (x == 7 && y == 7) answer++;
    else {
      // 도착을 안했으면, 상하좌우 반복을 위해 4까지 반복  
      for (int i = 0; i < 4; i++) {
        // 이동 좌표를 구하기  
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 각종 조건 체크하기 (배열 넘어가지 않게)
        if (nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7 && board[nx][ny] == 0) {
          // 이동한 곳을 방문으로 체크한다.  
          board[nx][ny] = 1;
          // 다음 단계를 진행/반복한다.
          DFS(nx, ny);
          // 다시 미방문으로 체크한다.
          board[nx][ny] = 0;
        }
      }
    }
  }

  public static void main(String[] args) {
    Main T = new Main();
    Scanner kb = new Scanner(System.in);
    board = new int[8][8];
    for (int i = 1; i <= 7; i++) {
      for (int j = 1; j <= 7; j++) {
        board[i][j] = kb.nextInt();
      }
    }
    board[1][1] = 1;
    T.DFS(1, 1);
    System.out.println(answer);
  }
}