Q. (X)

---

77 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격
자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격
자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.
▣ 입력설명
77 격자판의 정보가 주어집니다.
▣ 출력설명
첫 번째 줄에 경로의 가지수를 출력한다.
▣ 입력예제 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

전략

• DFS로 완전탐색
  cf. 3중 for문으로 풀기
• 하나하나 디버깅 하려고 하지말고, 대략 느낌만 가지면 됨
• 행, 열 헷갈리는거 주의
  

정답

import java.util.*;
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){
		// 종착점
		if(x == 7 && y == 7) answer++;
		else{
			// 현재 칸(x,y)에서 네가지 방향을 탐색
			for(int i=0; i<4; i++){
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				// 이동 가능한 범위 
				// nx>=1&&nx<=7&&ny>=1&&ny<=7 : 경계선 안쪽
				// board[nx][ny]==0 : 통로
				if(nx>=1&&nx<=7&&ny>=1&&ny<=7 && board[nx][ny]==0){
					// 추후 다시 방문하지 않기 위해 벽(1)으로 체크하고 이동
					board[nx][ny]=1;
					// 이동
					DFS(nx, ny);
					// 백트레킹(pop) 시  체크 풀어준다.
					board[nx][ny]=0;
				}
			}
		}
	}	
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		// 인덱스 0은 사용 X
		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);
	}
}