7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격 자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면
위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.
[입력설명]
7*7 격자판의 정보가 주어집니다.
[출력설명]
첫 번째 줄에 경로의 가지수를 출력한다.
입력예제 1
0000000
0111110
0001000
1101011
1100001
1101100
1000000
출력예제 1
8
문제 풀이
코드
- 코드의 전체 원리는 다음과 같다
- 4방향탐색을 통해 풀 수 있다. 봉우리(4방향 탐색) 문제 참고
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(board){
let answer=0; //카운팅
let dx=[-1, 0, 1, 0]; //행의위치
let dy=[0, 1, 0, -1]; //열의위치
function DFS(x, y){
if(x===6 && y===6) answer++; //6행 6열 도착했을 때(도착) 카운팅
else{
//네방향 탐색
for(let k=0; k<4; k++){
let nx=x+dx[k]; //nx는 행의 좌표
let ny=y+dy[k]; //ny는 열의 좌표
//갈 수 있는 경우(가장자리 제외, 벽(board[nx][ny]===1) 제외)
if(nx>=0 && nx<=6 && ny>=0 && ny<=6 && board[nx][ny]===0){
board[nx][ny]=1; //체크
DFS(nx, ny);
board[nx][ny]=0; //뒤로 빽할 때, 체크했던 것 풀어줌
}
}
}
}
board[0][0]=1;
DFS(0, 0);
return answer;
}
let arr=[[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]];
console.log(solution(arr));
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/18
지나간 길은 1로 바꿔주기