[Ch.08 - DFS] 12. 미로탐색

10. 미로탐색(DFS)

 

설명

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

---

문제 풀이 순서

1. ds 선언
   1. 현재 위치 변수
   2. 지나간 위치인지 확인 배열
   3. 카운트 배열
   4. 큐
2. 큐가 비어있을 때까지
   1. 이동가능 배열 선언
   2. 이동가능 배열 돌면서 체크
      1. 범위 안인지 밖인지
      2. 벽인지 통로인지
      3. 지나간 위치인지 아닌지
      4. 모두 통과할 경우
         1. 큐에 넣고
         2. 카운트 하고
         3. 지나간 위치로 체크

문제 구현 순서

---

 

+) 세련된 풀이

import java.util.Scanner;

//미로탐색 DFS
class Main {
	static int[][] board;
	static int answer = 0;
	// 격자판과 결과값 변수 정의

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	// 격자판 상하좌우 이동을 위한 변수 생성
	// 순서대로 12시 3시 6시 9시 방향

	public void DFS(int x, int y) {
		if (x == 7 && y == 7) {
			answer++;
		} else {
			for (int i = 0; i < 4; i++) {
				// 4방향 이동을 위한 반복문
				int nx = x + dx[i];
				int ny = y + dy[i];
				// next x와 next y 설정
				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];
		// 1번인덱스부터 사용
		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);
	}

}

 

 

(1) Pos 미로의 위치를 나타내는 함수와 가능한 위치인지 확인하는 메서드 작성

(2) 초기값 설정 

(3) 초기값에 이동가능한 거리를 나타내는 dis배열을 이용해, DFS 구성

(4) 중단 조건 : 목적지에 도달할 경우 결과값에 +1하고 리턴

(5) DFS가 돌때마다 벽인지 체크하는데, 벽이 아닐경우 DFS를 돌고, 돈 이후에 0으로 다시 초기화

 

import java.util.Scanner;
class Pos{
  public int x, y;
  Pos(int x, int y){
    this.x=x;
    this.y=y;
  }
  public boolean isValid(int width, int height){
    if(x<0||x>=width){
      return false;
    }
    if(y<0||y>=height){
      return false;
    }
    return true;
  }
}
public class Main {
  static int n=7;
  static int answer=0;
  static int[][] arr;
  static final int[][] dis = {{0,1},{0,-1},{1,0},{-1,0}};
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    arr= new int[n][n];
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        arr[i][j]=in.nextInt();
      }
    }
    Pos s = new Pos(0,0);
    DFS(s,0);
    System.out.println(answer);
  }
  static void DFS(Pos p, int L){
    arr[p.x][p.y]=1;
    
    if(p.x==6 && p.y==6){
      answer++;
      return;
    }
    else{
    for(int i=0;i<4;i++){
      Pos ns =new Pos(p.x+dis[i][0], p.y+dis[i][1]);
      if(ns.isValid(n,n)&&arr[ns.x][ns.y]==0){
        DFS(ns,L+1);
        arr[ns.x][ns.y]=0;
      }
      
    }
    }
  }
}