[알고리즘]DFS - 미로탐색

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램

출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로다.

import java.util.Scanner;

public class Main { 
	static int n, answer = 0;
	static int[][] maze;
	static int[] dx = {-1,0,1,0}, dy = {0,1,0,-1}; // direction
	
	public static void DFS(int x, int y) { 
		if (x==n && y==n) answer++; // 도착점
		else {
			for (int i=0; i<4; i++) {
				int nx = x+dx[i]; // next x
				int ny = y+dy[i]; // next y
				if (nx>=1 && nx<=n && ny>=1 && ny<=n && maze[nx][ny]==0) {
					maze[x][y] = 1; // 왔던 길로 되돌아가지 않음
					DFS(nx,ny); // 이동
					maze[x][y] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = 7;
		maze = new int[n+1][n+1]; // 7*7 미로
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) {
				maze[i][j] = scanner.nextInt();
			}
		}
		maze[1][1] = 1;
		DFS(1, 1);
		System.out.println(answer);
	}

}

 

---

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