LeetCode - 433. Minimum Genetic Mutation (python)

https://leetcode.com/problems/minimum-genetic-mutation/description/?envType=study-plan-v2&envId=top-interview-150

• 난이도 : medium
• 알고리즘 : BFS

접근방법

• 한 유전자에 변이가 일어난 스트링을 bank 안에 있는 스트링과 비교하지 말고 현재 유전자를 자리 별로 A, C, T, G로 바꿨을 때 해당 스트링이 bank에 있는지를 검사한다.
• 한 곳에 변이가 일어난 유전자 스트링이 bank에 어러 개 있을 수 있으므로 BFS를 사용하여 가장 빠른 경로의 변의를 찾는다.

소스코드

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        bankSet = set(bank)
        if endGene not in bankSet:
            return -1
        
        dq = collections.deque()
        geneLength = len(startGene)
        curGene = startGene
        count = 0
        dq.append((curGene, 0)) # (curGene, depth)

        while dq:
            curGene, depth = dq.popleft()
            if curGene == endGene:
                return depth

            for i in range(geneLength):
                for c in "ACGT":
                    newGene = curGene[:i] + c + curGene[i+1:]
                    if newGene is not curGene and newGene in bankSet:
                        bankSet.discard(newGene)
                        dq.append((newGene, depth + 1))
        
        return -1