백준 1697번: 숨바꼭질 (javascript, bfs)

쉬운 문제이나 또 어려운 문제였다. 시간제한도 넉넉하고 문제도 쉬우나 그 시간제한을 맞추게 알고리즘을 짜는게 쉽지 않았다. 

 

가장 빠른 시간, 즉 최소를 묻는 경우는 보통 풀이 알고리즘이 그리디, DP, BFS가 있다. 그 중에 BFS를 이용해 풀었는데 왜냐하면 수빈이가 이동할 수 있는 경우의 수가 3가지로 정해져 있기 때문이다.

 

처음 푼 풀이는 visited 집합과 queue를 동시에 사용해서 그 점에 방문한 적이 없으면 queue에 넣는 식으로 풀이를 짰다. BFS이므로 queue에 현재 위치와 움직인 시간을 동시에 넣어서 움직인 시간을 계산하고자 했다.

 

const fs = require('fs');
let [N, K] = fs.readFileSync("/dev/stdin").toString().trim().split(' ').map(a => Number(a))

function BFS(x, k){
    let queue = [[x,0]]
    let visited = new Set()
    visited.add(x)
    while(queue.length){
        let [y, cnt] = queue.shift()
        if(y === k){
            return cnt
        }
        for(const move of [y-1, y+1, 2*y]){
            if(move <= 100001 && !visited.has(move)){
                queue.push([move, cnt+1])
                visited.add(move)
            }
        }
    }
}

const answer = BFS(N, K)
console.log(answer)

그러나 52%에서 계속 시간초과가 나서 더 빠른 알고리즘이 필요했다. 개선점으로는 두가지가 떠올랐는데 하나는 cnt를 쓰지 않는 것이고 나머지는 set대신 다른 방법으로 방문 체크를 하는 것이다. 왜냐하면 집합은 집합안에 그 원소가 있는지를 확인하는데는 O(1)이 들지만 집합에 원소를 넣는데 O(N)이 들기 때문이다. 따라서 배열을 사용하는 것과 다를게 없다 생각했고 DP풀이를 생각하다 새로운 방법을 떠올렸다.

배열의 원소에 접근하고 초기화 하는 데 O(1)밖에 들지 않으므로 배열에 접근하고 초기화하는 방법만으로 방문을 확인하고 걸리는 시간까지 한번에 해결하는 방법이다.

 

그 풀이는 다음과 같다.

const fs = require('fs');
//let [N, K] = fs.readFileSync("/dev/stdin").toString().trim().split(' ').map(a => Number(a))
let [N, K] = fs.readFileSync("input.txt").toString().trim().split(' ').map(a => Number(a))

function BFS(x, k){
    let queue = [x]
    while(queue.length){
        let y = queue.shift()
        if(y === k){
            return array[y]
        }
        for(const move of [y-1, y+1, 2*y]){
            if(move <= 100001 && !array[move]){
                queue.push(move)
                // 걸리는 시간 체크
                array[move] = array[y]+1
            }
        }
    }
}

const MAX = 100001
array = new Array(MAX).fill(0)
const answer = BFS(N, K)
console.log(answer)

DP와 비슷하게 미리 배열을 생성한다. 수빈이와 동생의 위치의 최대값은 100000이므로 100001 크기의 배열을 생성하고 0으로 초기화 한다. 그리고 새로운 점을 방문할 때 이전 점, 배열의 좌표에 1을 더해줌으로써 걸리는 시간을 같이 체크한다.