10. 미로탐색(DFS)

 

설명

도착점까지 갈 수 있는 방법의 수는 몇가지 인가?

 

 

예시

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

 

8

 

 

 

 

풀이

처음에 1로 막아두고 dfs 돌고난다음에는 0으로 다시 해제해주어야한다.

import java.util.*;
class Main {
	static int ans;
	static int [][] board = new int[8][8];
	
	static int [] dx= {0,1,0,-1};
	static int [] dy= {-1,0,1,0};
	
	public void DFS(int x, int y) {
		
		if(x==7 && y==7) {
			ans++;
		}else {
			for(int i=0; i<4; i++) {
				int nx= x+dx[i];
				int ny= y+dy[i];
				
				if(nx>=1&& ny>=1 && nx<=7 && 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 sc = new Scanner(System.in);
		
		for(int i=1; i<=7; i++) {
			for(int j=1; j<=7; j++) {
				board[i][j]=sc.nextInt();
			}
		}

		board[1][1]=1;
		T.DFS(1,1);
		System.out.println(ans);
	}	
}