[LeetCode] 752. Open the Lock (Daily Question)

문제

---

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.

 

deadends(여기에 들어있는 번호로는 돌릴 수 없음), target(정답 번호)이 주어졌을 때,

4자리 번호 자물쇠를 풀기위해 번호를 돌리는 최소 횟수를 구하는 문제이다.

한번 돌릴 때는 한 칸 씩만 돌릴 수 있다. 1->2, 0->9 

 

문제로 예를 들면 deadends=["1000"], target="3000" 이렇게 주어졌을 때,

0000 -> 1000 -> 2000 -> 3000 이렇게 돌리면 최소 횟수(3)로 자물쇠를 풀 수 있지만,

deadends에 1000이 들어있으므로,

0000 -> 0100 -> 1100 -> 2100 -> 2000 -> 3000 이렇게 1000을 피해가야 한다. (5)

 

 

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".

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

 

풀이

---

아이디어

- 모든 자물쇠 번호(0000~9999)를 노드라 생각하여 BFS로 탐색한다.

- 간선은 각 노드에서 1번 돌렸을 때 도달할 수 있는 노드로 연결한다. (0000 : 1000, 9000, 0100, 0900 ...]

- 탐색한 노드는 방문처리를 하여 중복 탐색을 방지한다.

- deadends는 이미 방문한 것으로 처리한다.

 

BFS로 탐색하면 다음 탐색할 노드가 매 재귀마다 8배씩 늘어난다고 생각할 수 있지만, 방문한 노드를 체크한다면 10000번 이상을 탐색하진 않게 된다.

코드

class Solution:
    answer = -1

    # BFS 탐색
    def search(self, nodes, depth):
        # 다음 노드가 없는 경우
        if not nodes: return
        # 노드 방문 표시
        for node in nodes:
            self.visited[int(node)] = True

        next_nodes = set([])
        for node in nodes:
            # 목표 노드에 도달하면 끝
            if node == self.target: 
                self.answer = depth
                return
        
            for next_node in self.conns[node]:
                if not self.visited[int(next_node)]:
                    next_nodes.add(next_node)
        
        self.search(list(next_nodes), depth+1)

    def openLock(self, deadends: List[str], target: str) -> int:
        self.target = target

        # 예외처리
        if target == "0000": return 0
        if "0000" in deadends: return -1

        # 방문 테이블; deadend는 제외(=이미 방문 처리)
        self.visited = [False for _ in range(10000)]
        for deadend in deadends:
            self.visited[int(deadend)] = True

        # 노드의 연결 생성
        conns = {}
        for i in range(10000):
            i = str(i).zfill(4)
            conns[i] = []
            for j in range(4):
                conns[i].append(i[:j]+str((int(i[j])+9)%10)+i[j+1:])
                conns[i].append(i[:j]+str((int(i[j])+1)%10)+i[j+1:])

        self.conns = conns

        self.search(["0000"], 0)

        return self.answer

 

---

 

후기

---

난이도

처음에는 그래프문제라고 생각하지 못해 많이 해맸다.

그래프라 생각한 다음에도 deadends를 잘 처리하지 못해 시간초과가 나기도 했다.

조금 까다로운 문제였지만, 이런 문제도 그래프로 풀 수 있다는 것을 배울 수 있어서 좋았다.