[LeetCode] 752. Open the Lock, Medium

1. 문제

• 4자리 문자열로 구성된 deadends 배열과 target 문자열이 주어질 때, 몇 번의 과정을 거쳐서 target 문자열에 도달할 수 있는지 반환하라. 불가능하면 -1을 반환

2. 해결

function openLock(deadends: string[], target: string): number {
    const deadSet = new Set(deadends);
    if(deadSet.has("0000")) return -1;

    const queue: [string, number][] = [["0000",0]]
    const visit = new Set<string>();
    visit.add("0000");

    while(queue.length > 0) {
        const [curr, turns] = queue.shift();

        if(curr === target) return turns;

        const states = []
        for(let i =0 ; i< 4; i++) {
            for(const diff of [-1, 1]) {
                const newDigit = ((10 + diff + Number(curr[i])) % 10).toString();
                const newState = curr.slice(0,i) + newDigit + curr.slice(i+1);
                states.push(newState);
            }
        }

        for(const next of states) {
            if(!visit.has(next) && !deadSet.has(next)) {
                visit.add(next);
                queue.push([next, turns+1])
            }
        }
    }

    return -1;
};

• 일단 풀지는 못했다. 너무 어렵다.
• 원리는 큐에 문자열과 회전 수를 함께 담고, 별도 visit 배열을 두어 방문 여부를 체크한다.
• 여기서 인접 노드를 나는 각 숫자로 놓고 생각해봤는데, 그렇게 하면 안되고 한 번의 변경으로 이동되는 상태를 노드로 정의해야 한다. 즉, 0000에서 인접 노드는 1000, 0100, 0010, 0001, 9000, 0900, 0090, 0009가 된다. 얘네를 deadend와 visit 여부를 확인해서 큐에 넣어주고, 꺼낼 때 조건에 맞으면 turns를 반환하면 된다.