기타

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

히어로맛쿠키 2022. 2. 28. 19:36

 

(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);
  }

 

 

 

반응형