숨바꼭질 13913 시간초과&답안 차이

1. 문제 상황 설명

처음엔 isDone 변수를 이용해서 동생을 찾으면 while문을 탈출하려고 했다.
하지만 예상과 달리 시간 초과가 발생했다.

2. 원인 분석

isDone을 true로 만들어도 현재 shift한 current에 대해 current+1, current-1, current*2, 세 방향 전부 다 for문으로 돌고 난 다음에야 while문 조건을 검사할 수 있다.

즉, 동생을 찾았다고 바로 탈출하는 게 아니라, current의 다른 방향 탐색도 모두 끝내야 했다.
이 과정에서 queue에 불필요한 값들이 계속 추가되었고, 이로 인해 shift 연산(O(N)) 비용이 누적되어 시간초과가 났다.

시간초과 코드

const { start } = require("repl");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const [N, K]=input.shift().split(' ').map((el)=>+el);

// 가장 빠른 시간
let visited=new Array(100001).fill(-1);
// 어떻게 이동해야 하는지. 2차원 배열은 안됨 way 배열 두고 거기에 위치 저장..? 이동 경로용...
let way=new Array(100001).fill(-1);


let queue=[];
queue.push(N);
visited[N]=0;

let isDone=false;

while(isDone===false){
    let current=queue.shift();
    
    for (let next of [current+1, current-1, current*2]){
        if (next<0||next>=100001){
            continue;
        }

        // 아직 방문 안한 곳이면
        if (visited[next]===-1){
            visited[next]=visited[current]+1;
            way[next]=current;
            queue.push(next)
             // 동생이 있는 곳이라면
            if (next===K){
                isDone=true;
            }
        } 
    }
}

let path=[]
let temp=K;

while(temp!==-1){
    path.push(temp)
    temp=way[temp]

}
console.log(visited[K])
console.log(path.reverse().join(' ').trim())

3. 해결 방법

해결 방법은, current를 꺼냈을 때 즉시 검사하는 것이다.

즉, current === K인지 먼저 체크하고, 맞으면 바로 while문을 끊는다.
더 이상 current의 이동(next)들을 만들 필요가 없다.

for문 돌기 전에 current === K 여부를 먼저 검사하고, 맞으면 바로 isDone = true 하고 break하여 불필요한 next push 없이 탈출

정답 코드

const { start } = require("repl");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const [N, K]=input.shift().split(' ').map((el)=>+el);

let visited=new Array(100001).fill(-1);
let way=new Array(100001).fill(-1);

let queue=[];
queue.push(N);
visited[N]=0;

let isDone=false;

while(isDone===false){
    let current=queue.shift();
     if (current===K){
                isDone=true;
     }
    
    for (let next of [current+1, current-1, current*2]){
        if (next<0||next>=100001){
            continue;
        }
       
        if (visited[next]===-1){
            visited[next]=visited[current]+1;
            way[next]=current;
            queue.push(next)         
        } 
    }
}

let path=[]
let temp=K;

while(temp!==-1){
    path.push(temp)
    temp=way[temp]

}
console.log(visited[K])
console.log(path.reverse().join(' ').trim())