[LeetCode] 752. Open the Lock

😎풀이

1. 초깃값(0000)이 활용 불가하거나, 목표값과 동일하다면 즉시 반환
2. 자물쇠를 각 자리마다 한 칸 위로 혹은 한 칸 내린다.
3. 이미 시도했던 작업이라면 추가 시도하지 않는다.
4. 목표하는 수와 같아졌다면, 소요된 횟수를 반환한다.

function openLock(deadends: string[], target: string): number {
    const deadSet = new Set(deadends)
    if(target === '0000') return 0
    if(deadSet.has('0000')) return -1
    deadSet.add('0000')
    const queue: [string, number][] = [['0000', 0]]
    while(queue.length > 0) {
        const [curr, turn] = queue.shift()
        if(curr === target) return turn
        for(let i = 0; i < 4; i++) {
            const upDigit = ((Number(curr[i]) + 1) % 10)
            const up = curr.slice(0, i) + upDigit + curr.slice(i + 1)
            if(!deadSet.has(up)) {
                deadSet.add(up)
                queue.push([up, turn + 1])
            }
            const downDigit = ((Number(curr[i]) + 9) % 10)
            const down = curr.slice(0, i) + downDigit + curr.slice(i + 1)
            if(!deadSet.has(down)) {
                deadSet.add(down)
                queue.push([down, turn + 1])
            }
        }
    }
    return -1
};