[LeetCode 752] Open the Lock

Problem Link

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".

Example3

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation: We cannot reach the target without getting stuck.

Solution

• 문제의 핵심을 정리하자면 이렇다.

  lock이 걸려있는 4 circular wheels를 돌려 자물쇠를 풀고 싶다.

  • 0~9까지의 총 10개의 slots이 존재하며 0은 9로 9는 다시 0으로 돌아간다.
  • 초기에는 '0000'으로 initialize하여 암호를 풀어 나갈 것이다.
  • 그러나 만약, slot을 돌리면서 얻어진 trial number가 Input으로 주어진deadends의 배열의 원소와 같은 경우가 발생한다면 stop turning 상태가 된다.
  • 따라서 deadends의 원소가 되지 않으면서 최소 횟수로 각 slot을 돌려 target인 상태로 만들어야 한다.

• 우선 0-9의 10가지 경우를 갖는 slot이 총 4개 있기 때문에 전체 $10^4$개의 경우의 수로 계산되어 완전 탐색으로 충분히 가능한 숫자다.

• 신경써 주어야 할 부분은 0일 때 9로 넘어가는 것과 9일 때 0으로 넘어가는 것이었다.

  • 이는 +1 혹은 -1로 조절되는 delta를 더할 때 % 10으로 표현해주면 된다.

• 전체적인 로직은 queue와 방문 처리 visited 배열을 이용한 BFS 탐색 방식을 선택하였다.

  • 그런 다음 trial number가 아직 방문하지 않았으면서 deadends에 포함되지 않으면 queue에 turn_time+1과 함께 집어 넣어 탐색을 반복한다.

  • BFS 탐색이다보니 queue에서 뽑아낸 원소가 target과 같은 상황이 나타난다면 그 때의 turn_time이 최소 깊이이므로 이를 반환하면 된다.

소스 코드

from collections import deque

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if target == "0000":
            return 0  # direct
        if "0000" in deadends:
            return -1

        q = deque([("0000", 0)])  # now_dial, turn_time
        visited = set("0000")
        
        while q:
            now_dial, turn_time = q.popleft()
            if now_dial == target:
                return turn_time

            for i in range(4):
                for delta in [+1, -1]:  # control
                    tmp = (int(now_dial[i]) + delta) % 10  # 0 to 9 or 9 to 0
                    nxt_dial = now_dial[:i] + str(tmp) + now_dial[i+1:]
                    if nxt_dial not in visited and nxt_dial not in deadends:
                        visited.add(nxt_dial)
                        q.append((nxt_dial, turn_time+1))

        return -1

참고

• Python의 -1 % 10이 9를 출력하는 이유?

  • -1 % 10을 계산할 때, 파이썬은 다음과 같은 공식을 사용한다.

    -1 = 10 * (-1) + 9

  • 다른 언어는 어떻게 계산하는지? (by ChatGPT)

    1. C/C++: 이 언어들에서는 나머지의 부호가 피제수(나누어지는 수)의 부호를 따릅니다. 따라서, -1 % 10은 -1을 반환합니다.
    2. Java: Java에서도 C/C++과 유사하게 나머지의 부호는 피제수의 부호를 따릅니다. 그래서 -1 % 10은 -1이 됩니다.
    3. JavaScript: JavaScript에서는 나머지의 부호가 피제수의 부호를 따르기 때문에, -1 % 10의 결과는 -1입니다.
    4. Ruby: Ruby에서도 파이썬과 유사하게 나머지 연산의 결과는 양수가 됩니다. 그래서 -1 % 10은 9가 됩니다.