[PS] 인프런 강의 - DFS 10. 미로탐색

 

문제

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

풀이

 

미로의 값을 이차원 배열에 저장해둔다.

위, 오른쪽, 아래, 왼쪽 방향으로 한 칸씩 이동할 수 있는데 x, y 좌표상으로 나타내면

 

• 위: (-1, 0)
• 오른쪽: (0, 1)
• 아래: (1, 0)
• 왼쪽: (0, -1)

 

이렇게 된다. 다음과 같이 배열을 선언해서 사용하면 된다.

 

int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

 

위 조합을 사용해서 이동할 좌표가, 경계선 안쪽에 있고 통로인 경우(미로의 값이 0) 미로의 값을 1로 변경해주고

DFS(이동할 좌표) 를 호출한다. 호출이 끝난 뒤에는 다시 돌아왔을 때 (다른 경우의 수를 따져야하니까) 미로의 값을 다시 0을 바꿔준다.

 

주의 할 점: 출발점 1,1 이후로 가는 방법의 경우의 수를 구해야 하므로 1,1은 방문했다고 치고 시작해야한다.

 

 

코드

import java.util.Scanner;

public class Main {
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int[][] board;
	static int answer = 0;
	
	public static void DFS(int x, int y) {
		if(x== 7 && y==7) { //도착하면 카운트
			answer++;
		}
		else {
			for(int i=0; i<4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				//경계선 안쪽에 있는지, 통로(0)인지 체크
				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) {
        Scanner in = new Scanner(System.in);
        
        board = new int[8][8]; //출발점이 1,1
        for(int i=1; i<=7; i++) {
        	for(int j=1; j<=7; j++) {
        		board[i][j] = in.nextInt();
        	}
        }
        
        board[1][1] = 1; //주의!! 출발
        DFS(1,1);
        System.out.println(answer);
        
    }
}