39. Open the Lock(bfs)

문제

각각 0-9까지의 숫자로 된 슬롯이 4개 있는 자물쇠가 있다.

자물쇠는 '0000'에서 시작한다.

한 슬롯은 1에서 2로도, 2에서 1로 움직일 수 있다.

하지만 한 번에 한 칸만 움직일 수 있다.

 

한 번 입력하면 자물쇠를 다시 열지 못하게 되는 숫자 조합 deadends를 배열로 받는다.

자물쇠를 푸는 비밀번호 target을 인수로 받아 최소 몇 번을 돌려야 자물쇠를 열 수 있는지 구하시오.

여는 것이 불가능하다면 -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".

 

해결 방법

https://www.youtube.com/watch?v=Pzg3bCDY87w

그래프 문제에서 최단거리를 찾을 때 bfs가 유리하다. 

이 경우에서도 마찬가지이다.

 

'0000'에서 시작해서 '0009'를 찾는 경우를 가정해보자.

0000에서 나올 수 있는 경우의 수는 8개이다.

각 경우의 수에서는 또 각각 8개씩의 경우의 수가 나올 수 있다.(deadend가 아닌 이상)

이 경우 dfs를 사용하면 한 가지에서 나올 수 있는 모든 경우의 수를 탐방해야 하는데 그럼 시간이 너무 많이 걸린다.

이 때는 bfs를 사용하면 0009를 금방 찾을 수 있다. 

https://leetcode.com/problems/open-the-lock/discuss/201608/Python-BFS

from collections import deque

class Solution:
    def openLock(self, deadends, target):
        # 검색 속도를 높이기 위해 리스트가 아닌 hash set 사용
        dead_set = set(deadends)
        queue = deque([('0000', 0)])
        visited = set(['0000'])

        while queue:
            string, steps = queue.popleft()
            if string == target:
                return steps
            elif string in dead_set:
                continue

            for i in range(4):
                digit = int(string[i])

                # move가 -1인 경우 : 네 슬롯 중 한 슬롯을 아래로 한 칸 움직였을 때 나오는 조합 생성
                # move가 1인 경우 : 네 슬롯 중 한 슬롯을 위로 한 칸 올렸을 때 나오는 조합 생성
                for move in [-1, 1]:
                    new_digit = (digit + move) % 10
                    new_string = string[:i]+str(new_digit)+string[i+1:]

                    # 나온 조합 visited에 넣고 queue에 steps와 함께 추가
                    if new_string not in visited:
                        visited.add(new_string)
                        queue.append((new_string, steps+1))
                        
        # queue를 다 확인했는데도 조합이 나오지 않았으면 없다는 뜻
        return -1