[BOJ] 12851: 숨바꼭질 2(node.js)
🔗 문제 링크
https://www.acmicpc.net/problem/12851
💬 문제
🤔 접근
숨바꼭질과 비슷한 문제로, BFS를 통해 각 숫자에 도착하는 최소 시간을 계산하면 되는 것 같았다. 하지만 단순 최소 시간만 구하는 것이 아닌, 최소 시간으로 도달할 수 있는 경우의 수까지 추가로 구해줘야했다.
기존엔 visited 배열을 boolean으로 관리하여 true라면 큐에 추가하지 않는 방식을 사용했는데, 최소 시간으로 도달할 수 있는 여러 경우가 있을 수 있다보니 다른 방법 + 같은 최소 시간으로 특정 숫자에 도달하는 경우도 큐에 넣어 처리를 해줘야했다.
따라서 visited 배열을 -1로 초기화한 후, 도달하는 시간으로 덮어쓰자고 생각했다.
⚠️ 문제
처음 visited 처리 과정에서 시간 비교를 잘못하고 있었다.
if(visited[nx] > time + 1) continue;
로 처리하고 있었는데
일단 부등호 방향이 반대였고, 나는 visited 배열을 -1로 초기화했기 때문에 부등호 방향을 바꾸더라도 큐에 숫자가 들어가지 않고 while문이 종료될 것이었다.
✏️ 해결
조건문을 (첫방문 || 이전 방문 시간과 같다면) 으로 수정했다.
BFS는 특정 점에 처음 도달했을 때가 최소 거리라서, -1이 아니라면 해당 값은 최소로 도달할 수 있는 시간이다. 따라서 해당 시간보다 크다면 최소 거리가 아니기 때문에 큐 내부에 집어넣지 않고, 같다면 최소거리로 도달하면서 다른 경우의 수기 때문에 큐 내부 처리를 해준다.
const visited = Array(100001).fill(-1);
// ... bfs 로직 내부
if (visited[nx] === -1 || visited[nx] === time + 1) {
// 첫 방문 || 최소 시간으로 도달하는 다른 경우
visited[nx] = time + 1;
}
//🤔 깨달은 점
BFS는 해당 점에 처음 도달할 때가 항상 최소 거리이다!
이게 제일 중요한 포인트인 것 같다.
visited 배열을 boolean이 아닌 도달한 시간으로 만들어보자는 접근은 잘 했다고 생각한다!
✅ 전체 코드
//숨바꼭질2 #12851
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [start, end] = input[0].split(' ').map(Number);
const queue = [];
const visited = Array(100001).fill(-1);
let head = 0;
let tail = 0;
queue[tail++] = [start, 0];
visited[start] = 1;
let found = false;
let count = 0;
let minTime = Number.MAX_SAFE_INTEGER;
while (head < tail) {
const [cur, time] = queue[head++];
if (cur === end) {
if (!found) {
minTime = time;
found = true;
count = 1;
} else {
count++;
}
continue;
}
for (let nx of [cur - 1, cur + 1, cur * 2]) {
if (nx < 0 || nx > 100001) continue;
if (visited[nx] === -1 || visited[nx] === time + 1) {
visited[nx] = time + 1;
queue[tail++] = [nx, time + 1];
}
}
}
console.log(minTime + '\n' + count);B
u
y
M
e
A
C
o
f
f
e
e
☕
️