DFS | 재귀함수 미로찾기 구현 (Java)

 

(1, 1)에서 시작하여 (N, M)까지 반드시 도착하는 미로가 있다. 

미로를 탈출하는 최단거리를 반환하는 문제다.

 

일단 결과 시각화다. 

1은 길,

0은 벽,

2는 밟아간 자리

3은 되돌아간 자리

 

* 참고 : 행렬의 변화 과정을 gif로 시각화하는 모듈을 만들어두었다.

integer(0~9) array change process visualization (how to make gif)

 

 

나는 가장 먼저 DFS로 풀었다. 

BFS로 푸는 방법도 있는데 DFS를 먼저 기록한다.

 

DFS로 구현하고자 했던 이유:

1. (1,1)에서 (N,M)으로 가는 미로 최단거리 : 최대한 우측하단 방향으로 가면 된다.

2. 미로는 일단 깊게 쑥 들어가보는 알고리즘이 적합할 거라고 생각했다.

=> 즉, 최대한 우측하단으로 DFS로 파고들어가면 빨리 찾을 수 있지 않을까? 라는 생각

 

 

---

알고리즘

요약 :

일단 갈 수 있는 길(1)을 가면서 스택을 쌓고,

만약 되돌아가야 한다면 스택에서 빼고,

그렇게 쌓아올려가며 최종 목적지에 도착한다.

구현한 알고리즘에 따라 스택에 쌓여있는 개수는 최단거리다.

피니시 플래그가 뜨면 쫙 result++한다.

 

DFS(x, y)

  if (map[x][y]가 벽(0)이 아님)

    현위치 map[y][x] 방문처리

 

  // 종료조건

  if (y == N && x == M)

    종료플래그 = true

    종료위치 map[y][x] 방문처리

    return result++

 

  // 재귀부 : 어딘가 갈 길 (1) 이 있는 경우

  for (int i=0; i<4; i++)
    int nx = x + dx[i]
    int ny = y + dy[i]
    if (map[ny][nx] == 1) : DFS(ny, nx)
    if (finishFlag == true) return result++;

 

  // 갈 길이 없어 돌아가야 하는 경우

  map[y][x] = 3

  return 0;

 

 

 

---

구현 코드

 

DFS

  public static int N, M;
  public static int result = 0;
  public static boolean finishFlag = false;
  public static int[][] map = new int[200][200];

  // 이동 방향 정의 (하우상좌)
  // 우측하단을 먼저 고려하고자 한다
  public static int[] dx = {0, 1, 0, -1};
  public static int[] dy = {1, 0, -1, 0};

  
  public static int DFS(int y, int x){
    // map[y][x]에 서 있어도 되는지 판단
    if (map[y][x] == 0) return 0;
    map[y][x] = 2;

    // 종료조건
    if (y == N && x == M) {
      finishFlag = true;
      map[y][x] = 2;
      return result++;
    }

    // 갈 곳이 있는 경우 재귀
    // 미로를 찾았는데도 다른 i에서 이어서 길을 찾는 경우를 유의 
    // => finishFlag 설정
    for (int i=0; i<4; i++) {
      int nx = x + dx[i]; 
      int ny = y + dy[i];
      if (map[ny][nx] == 1) DFS(ny, nx);
      if (finishFlag == true) return result++;
    }
    
    // 돌아가야 하는 경우 (재귀로 갱신된 맵 반영)
    // 위 for문을 지나 왔다면 자동으로 map[ny][nx] != 1
    map[y][x] = 3;
    return 0;
  }

 

main

public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    // 맵 정보 로드
    N = sc.nextInt();
    M = sc.nextInt();
    sc.nextLine();
    for(int i=1; i<=N; i++){
      String line = sc.nextLine();
      for(int j=1; j<=M; j++){
        map[i][j] = line.charAt(j-1) - '0';
      }
    }

    // DFS
    DFS(1, 1);
    
    System.out.println(result);
  }