IF - 미로찾기

문제

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

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

입출력 예시

INPUT
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

OUTPUT
8

풀이 및 회고

• 미로 내에서 다음 칸으로 전진하기 위한 조건은
• 첫째. 전진하려는 칸의 값이 0 이어야 한다.
• 둘째. 전진하려는 칸은 이번 DFS 순회에서 방문한 적이 없는 칸이어야 한다.
• 셋째. 전진하려는 칸이 주어진 미로를 벗어나지 않는다.
• 위 세 조건 중 첫째, 둘째 조건은 이번 DFS 깊이에서 방문하려는 칸의 값을 1로 바꿈으로써 해결된다.
• 세 번째 조건은 현재 칸 좌표 (x,y) 에서 x+1, x-1, y-1, y+1 이 각각 0에서 6 사이인지 검사하여 해결한다.

코드

const solution = (maze) => {
	let answer = 0;
	const dx = [-1, 0, 1, 0];
	const dy = [0, 1, 0, -1];

	const DFS = (x, y) => {
		if (x === maze.length - 1 && y === maze.length - 1) {
			answer++;
		} else {
			for (let i = 0; i < 4; i++) {
				let nx = dx[i] + x;
				let ny = dy[i] + y;
				if (nx >= 0 && nx <= 6 && ny >= 0 && ny <= 6 && maze[nx][ny] === 0) {
					maze[nx][ny] = 1;
					DFS(nx, ny);
					maze[nx][ny] = 0;
				}
			}
		}
	};

	maze[0][0] = 1;
	DFS(0, 0);
	return answer;
};