728x90
728x90
문제설명
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 |
0은 지나 갈 수 있는 통로.
1은 지나 갈 수 없는 벽.
0,0 부터 시작해서
7,7로 도착하는 경우의 수를 구하는 함수를 완성하세요.
function solution(board) {
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));
접근방법
도저히 접근 할 수가 없었다.
풀이를 듣고 이해를 하긴 했는데,
설명하자니 막막하다.
function solution(board) {
let answer = 0;
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
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));
우선 answer에 0을 매겨 놓는다.
dx 와 dy 는 이동칸수를 나타낸다
x는 가로축 이고 y는 세로 축이다
dx[0], dy[0] 은 -1, 0 을 의미한다.
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++;
}
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));
if 문을 이용해 answer에 카운트를 해줄 조건문을 만든다.
x와 y가 모두 6일때
즉 6,6에 도달하면 answer에다가 1을 더해줄거다.
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++;
return;
}
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx >= 0 && nx <= 6 && ny >= 0 && ny <= 6 && board[nx][ny] === 0) {
board[x][y] = 1;
DFS(nx, ny);
board[x][y] = 0;
}
}
}
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)); //8
nx 는 next x 를 의미한다.
현재의 x값에다가 dx[i]값을 더해준다.
함수의 매개변수에 0,0이 할당 되었으니
x 와 y는 모두 0 이고
nx와 ny는 각각 dx[i] dy[i]를 더해준 값이 된다.
i는 for문을 통해 0부터 3까지 증가한다.
nx와 ny 가 0이상 6이하 이고,
board[nx][ny]가 0이면
board[x][y]에 1을 체크하고
재귀함수를 통해 DFS(nx,ny)를 호출하고 반복한다.
**
board[x][y] = 1 과
board[x][y] = 0 은
board[nx][ny] = 1
board[nx][ny] = 1
로 바꿔도 결과에 영향이 없었다.
728x90
728x90
'문제풀이 > 자료구조,알고리즘' 카테고리의 다른 글
아일랜드 (BFS) (0) | 2021.12.05 |
---|---|
아일랜드(DFS) (0) | 2021.12.05 |
송아지 찾기!(BFS) (0) | 2021.12.03 |
preorder/ inorder/ postorder 구현 (0) | 2021.12.01 |
댓글