Open the Lock

숫자 네 개가 달린 자물쇠를 특정 숫자로 만드는 문제. 각 숫자는 한번에 한 칸만 옮겨진다. 난점은 막다른 골목(deadend)의 존재. 깊이 우선 탐색으로 해결하면 된다. 

https://leetcode.com/problems/open-the-lock/

 

class Solution:
    def openLock( self, deadends, target: str ) -> int:
        deadends = set( deadends )
        currentNumbers = { '0000' }
        count = 0
        visitedNumbers = set()

        while currentNumbers:
            visitingNumbers = set()

            for currentNumber in currentNumbers - deadends:
                if target == currentNumber:
                    return count
                else:
                    visitedNumbers.add( currentNumber )
                    iterator = self.__iterateNearNumber( currentNumber, deadends )
                    visitingNumbers.update( iterator )

            visitingNumbers -= visitedNumbers
            currentNumbers = visitingNumbers
            count += 1

        return -1
    
    
    def __iterateNearNumber( self, number, deadends ):
    	'''이웃하는 숫자를 반복한다
        '''
        for order, digit in enumerate( number ):
            for digit in self.__getNearDigit( digit ):
                maskedNumber = self.__maskNumber( number, order, digit )

                if maskedNumber not in deadends:
                    yield maskedNumber


    def __getNearDigit( self, value ):
    	'''이웃하는 숫자를 얻는다
        '''
        if '9' == value:
            return [ '0', '8' ]
        elif '0' == value:
            return [ '9', '1' ]
        else:
            return [ chr( ord( value ) - 1 ), chr( ord( value ) + 1 ) ]


    def __maskNumber( self, number, order, digit ):
    	'''네 자리 숫자 조합
        '''
        return number[ : order ] + digit + number[ order + 1: ]