🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs
.readFileSync(path)
.toString()
.trim()
.split('\n')
.map((it) => it.split(' ').map(Number));
inputs.shift();
const map = Array(101).fill(0);
const q = [1];
const l = new Map();
for (const input of inputs) {
const [x, y] = input;
l.set(x, y);
}
while (q.length) {
const x = q.shift();
if (x === 100) {
console.log(map[x]);
break;
}
if (l.has(x)) {
const nx = l.get(x);
if (map[nx] === 0) {
map[nx] = map[x];
} else {
map[nx] = Math.min(map[x], map[nx]);
}
q.push(nx);
continue;
}
for (let i = 1; i <= 6; i++) {
const nx = x + i;
if (map[nx] === 0 || map[nx] > map[x] + 1) {
map[nx] = map[x] + 1;
q.push(nx);
}
}
}
🟢 풀이
⏰ 소요한 시간 : -
뱀과 사다리 게임이라고 해서 시뮬레이션 유형인 줄 알았다. 근데 아니었음
체스판 모양을 사용해서 인접행렬을 만들었는데 아니었음...
결국 뱀이 있는 칸을 밟든, 사다리가 있는 칸을 밟든 나의 의지와 상관 없이 움직이게 된다. 그렇기 때문에 구분할 필요 없이 뱀과 사다리를 통해 순간이동하는 시작위치를 키로 끝 위치를 인덱스로 하는 map을 만들어준다. 이 배열의 각 요소는 초기값이 0이며 요소 값은 각 좌표까지의 최단거리다.
그 후 1칸부터 100칸까지 가는 최단거리만 체크해주면 되기 때문에 BFS를 통해 구현 해주면 된다. 따라서 총 101칸의 1차원 배열을 만든다. (100칸에 1을 더해줘 0인덱스 마진처리) 그 후 시작 위치 1을 큐에 넣어주고, BFS 로직을 수행한다.
BFS 로직은 큐에 있는 맨 앞의 값을 빼서 그 값으로 이동을 해주면 된다.
만약 현재 위치인 x가 100이라면 도착점에 최단거리로 도착한 것이니까 정답을 출력한 뒤 반복문을 종료한다.
만약 현재 위치인 x가 도착점이 아니라면 사다리나 뱀과 연결되어 있는지 확인한다. 연결되어 있다면 뱀과 사다리로 이동했을 때의 최단거리를 체크해준다. 해당 좌표가 0이라면 미방문 상태이므로 현재 좌표의 값으로 최단거리로 갱신해준다. 만약 방문한 적이 있어 0이 아닌 숫자값이라면 현재 좌표의 최단거리와 비교해 최단거리를 갱신한다. 그 후 큐에 넣어놓고 continue해 다음 탐색을 한다. 해당 위치에선 강제로 이동해야 하기 때문에 아래의 주사위 로직이 필요 없기 때문이다.
만약 사다리나 뱀이 연결되어 있지 않은 경우는 주사위로 이동을 해야하는데 1부터 6까지 반복하며 모든 경우의 수를 탐색하며 미방문 상태이거나, 지금의 탐색이 최소값일 경우에만 큐에 넣어준다.
🔵 Ref
