미로문제들을 전부 모아 볼께요...
탈출 해봅시다.
계속 업데이트 예정
최단거리
최소거리
(내 인생 모토다)
모든경우의 수텍스트
미로탐색 개념
1번문제 (최단거리)
최단시간 / 최소거리
세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미합니다. 로봇은 지도 위를 일분에 한 칸씩 상하좌우로 이동할 수 있습니다. 로봇의 위치와 목표 지점이 함께 주어질 경우, 로봇이 목표 지점까지 도달하는 데 걸리는 최소 시간을 리턴해야 합니다.
예시
let room = [
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 1, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0],
[1, 0, 0, 0, 0, 0],
];
let src = [4, 2];
let dst = [2, 2];
let output = robotPath(room, src, dst);
console.log(output); // --> 8
문제풀이
const robotPath = function (room, src, dst) {
// TODO: 여기에 코드를 작성합니다.
// 로봇이 움직이는 함수를 만들어 보자
// 가로길이, 세로 길이, 시작점, 단계
const aux = (M , N, candi, step) => {
// 시작점
const [row, col] = candi;
// room을 벗어났을때
if (row < 0 || row >= M || col < 0 || col >= N) return;
// 길을 만났을때;
if (room[row][col] === 0 || room[row][col] > step){
room[row][col] = step;
} else {
return
}
//아래로 내려갈때
aux(M, N, [row + 1, col], step + 1);
aux(M, N, [row - 1, col], step + 1);
aux(M, N, [row, col + 1], step + 1);
aux(M, N, [row, col - 1], step + 1);
};
aux(room.length, room[0].length, src, 1)
const [r, c] = dst;
return room[r][c] - 1;
};2번문제 (모든 경우의 수)
모든경우의 수
7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격
자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격
자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면
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가지이다.
▣ 입력설명
7*7 격자판의 정보가 주어집니다.
▣ 출력설명
첫 번째 줄에 경로의 가지수를 출력한다.
문제풀이
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++;
else{
for(let k=0; k<4; k++){
let nx=x+dx[k];
let ny=y+dy[k];
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;
}3번문제
N * N의 크기를 가진 보드판 위에서 게임을 하려고 합니다. 게임의 룰은 다음과 같습니다.
좌표 왼쪽 상단(0, 0)에 말을 놓는다.
말은 상, 하, 좌, 우로 이동할 수 있고, 플레이어가 조작할 수 있다.
조작의 기회는 딱 한 번 주어진다.
조작할 때 U, D, L, R은 각각 상, 하, 좌, 우를 의미하며 한 줄에 띄어쓰기 없이 써야 한다.
예시: UDDLLRRDRR, RRRRR
한 번 움직일 때마다 한 칸씩 움직이게 되며, 그 칸 안의 요소인 숫자를 획득할 수 있다.
방문한 곳을 또 방문해도 숫자를 획득할 수 있다.
보드 밖을 나간 말은 OUT 처리가 된다.
칸 안의 숫자는 0 또는 1이다.
단, 좌표 왼쪽 상단(0, 0)은 항상 0이다.
획득한 숫자를 합산하여 숫자가 제일 큰 사람이 이기게 된다.
보드판이 담긴 board와 조작하려고 하는 문자열 operation이 주어질 때, 말이 해당 칸을 지나가면서 획득한 숫자의 합을 구하는 함수를 작성하세요.
예시
const board1 = [
[0, 0, 0, 1],
[1, 1, 1, 0],
[1, 1, 0, 0],
[0, 0, 0, 0]
]
const output1 = boardGame(board1, 'RRDLLD');
console.log(output1); // 4
생각하기
보드를 그래프로 옮겨보자
배열은 X,Y를 반대로 생각하면 끝*
시작 위치는 어디 인가.
(0,0)
좌우으로 움직이러면
x축에서 한칸 더하거나 빼주면 된다.
상하로 움직이려면
y축에서 한칸 더하거나 빼주면 된다.
그리고 보드에 벗어나는 조건은 생각해야한다.
x,y가 음수 일때 그리고 x,y가 보드길이보다 클때.
그땐 OUT!
첫번째 문제풀이
function boardGame(board, operation) {
// TODO: 여기에 코드를 작성하세요.
// 출발점 (0,0)
// x = 0
// y = 0
// 최종목표는 구하는 변수를 만든다.
let score = 0;
// 출발점
let x = 0;
let y = 0;
// 현재 위치 변수 설정
let current = board[0][0]
//반복문으로 움직이는 방향 설정
for(let i = 0; i < operation.length; i++){
if(operation[i] === 'U'){
y -= 1 , x += 0;
}
if(operation[i] === 'D'){
y += 1 , x += 0;
}
if(operation[i] === 'R'){
y += 0 , x += 1;
}
if(operation[i] === 'L'){
y += 0 , x -= 1;
}
//보드가 아웃일때!!!!!
if(x < 0 || y < 0 || board.length < y || board.length < x){
return 'OUT';
}
//현재 위치 설정
current = board[y][x];
score = score + current;
}
return score;
};두번째 풀이
1.보드의 말 움직임을 객체로 만든다.
2.out여부를 판단하는 함수를 만든다.
3.operation에 따라서 X축과 Y축을 움직이면서 스코어에 점수를 더해준다.
// LOOK UP TABLE을 사용한다면 조건문을 추상화시킬 수 있습니다.
function boardGame(board, operation) {
// TODO: 여기에 코드를 작성하세요.
const DIR = {
'U': [-1, 0],
'D': [1, 0],
'L': [0, -1],
'R': [0, 1]
}
const LEN = board.length;
const isValid = (y, x) => 0 <= y && y < LEN && 0 <= x && x < LEN;
let Y = 0;
let X = 0;
let score = 0;
for (let i = 0; i < operation.length; i++) {
const [dY, dX] = DIR[operation[i]];
Y += dY;
X += dX;
if (isValid(Y, X) === false) return 'OUT';
score += board[Y][X];
}
return score;
};