[Leetcode/파이썬] 433. Minimum Genetic Mutation

Minimum Genetic Mutation

---

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

• For example, "AACCGGTT" --> "AACCGGTA" is one mutation.

There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

 

Example 1:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

Example 2:

Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2

 

Constraints:

• 0 <= bank.length <= 10
• startGene.length == endGene.length == bank[i].length == 8
• startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].

 

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        q = deque()
        q.append((startGene, 0))    # startGene, cnt

        visited = set()
        visited.add(startGene)

        options = ['A', 'C', 'G', 'T']
        cnt = 0	# 오답노트(?) : 이건 필요없는 부분인데 문제 풀때 차마 지우지 못해서 남겨놓음.

        while q :
            curr, cnt = q.popleft()
            if curr == endGene :
                return cnt

            for option in options :
                for s in range(8) :
                    nxt = curr[:s] + option + curr[s+1:]
                    if nxt in bank and nxt not in visited :
                        visited.add(nxt)
                        q.append((nxt, cnt + 1))
        return -1

이게 무슨 문젠가 싶었는데 아래 힌트를 보고 BFS라는걸 알았다. 이게...?

문자열을 visited 로 받을 경우는 해쉬로 받는게 낫겠다 싶어서, 딕셔너리나 집합을 활용하는 게 좋을 듯 싶다. 그렇지 않더라도 좌표를 받게 되는 경우에도 집합을 활용해도 좋은 경우가 많이 있기 때문에 이런 연습도 중요할 것이라 생각한다.

처음에 다른 사람 코드를 보니까 cnt를 따로 빼서 while 문 안에 for문을 한 번 더 구현하여 여러번 돌아가게 하던데, 이거보다 차라리 큐에 (문자열, cnt) 튜플이나 리스트로 묶어서 넣어버리면 공간은 늘어나더라도 시간적인 측면에서 조금 더 줄일 수 있지 않을까? 생각이 들어 묶어서 처리해보았다. 

먼저 curr, cnt를 받아오고 정답처리를 해준다. 이런 구조는 연습해놓는게 좋을 것이다. 그 후 교체해 넣을 문자열, 전체 문자열이 8자로 구성되어 있기 때문에 다음과 같은 2중 for문을 구성하게 되었다. 

nxt는 한자씩 바꿀 예정이므로, s 자리 문자열을 제거하고 대체 문자열을 넣은 후, 이 문자열이 유효한 문자열이고, 방문하지 않은 문자열이면 visited에 추가, cnt + 1 을 하여 큐에 다시 넣어준다. 이때 visited를 구현하지 않으면 무한루프가 발생할 수도 있고, cnt가 지나치게 많이 발생할 수 있기 때문에 예외조항으로 구현해놓는 것이 좋겠다. 이렇게 돌았는데도 답이 나오지 않으면 -1을 리턴한다. 

전형적인 BFS문제인데 이런 문제를 처음 접해봐서 그런가 접근 방법이 떠오르지 않아 많은 분들의 코드를 참고했다. 풀이를 한 번 보고나니 다른 방법으로도 문제해결이 가능하겠다는 생각이 들었고 cnt를 묶어서 구현하게 되었다.