[LeetCode] 433. Minimum Genetic Mutation (Python)

LeetCode 433. Minimum Genetic Mutation
🗓️ Daily LeetCoding Challenge November, Day 2
String / BFS

https://leetcode.com/problems/minimum-genetic-mutation/

Minimum Genetic Mutation - LeetCode

1. 문제 설명

유전자 염기서열(문자열) start와 end가 주어지면 start에서 시작하여 end까지 변화시킬 수 있는지 물어보는 문제이다.

이때, 염기서열은 여덟 자리이며 'A', 'C', 'T', 'G' 4개만 존재한다. (DNA라 Uracil이 없는건가)

염기서열에서 돌연변이는 한 번에 한 자리만 가능하며 돌연변이 이후 염기서열이 bank에 속해야 한다.

 

아래와 같이 start, end, bank가 주어진다고 가정하자.

start = "AACCGGTT", end = "AAACGGTA"
bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

"AACCGGTT"에서 마지막 인덱스인 'T'가 'A'로 돌연변이를 일으켜 "AACCGGTA"로 변하고,

"AACCGGTA"에서 세 번째 인덱스인 'C'가 'A'로 돌연변이를 일으켜 "AAACGGTA"로 변한다.

 

start 염기서열이 end 염기서열까지 총 두 번의 돌연변이가 발생했으므로 2를 리턴하면 된다.

---

2. 문제 접근

BFS

너비우선탐색으로 주어진 문자열에서 최소 변화 횟수를 카운팅한다.

큐에서 꺼낸 임시 문자열을 nested loop로 돌린다.

outer loop에서 교체할 문자를 선택하고, inner loop에서 임시 문자열을 슬라이싱하여 새로운 문자를 끼워 넣는다.

만약 새로운 문자열이 bank에 있다면 해당 문자열을 카운팅을 하나 늘려서 큐에 넣는다.

 

기존에 BFS문제는 중복 방문을 방지하기 위해 visit list를 만들어 확인한다.

하지만 이 문제의 경우 염기서열 8자리에 올 수 있는 염기들을 모두 고려하여 visit list를 만들기 보다는

bank의 최대 원소 개수가 10개이므로 remove()를 이용하여 bank에서 제외해 주었다.

 

큐에서 꺼낸 임시 문자열이 end와 동일하면 즉시 리턴하면 된다.

---

3. 참고 사항

① DFS로도 해결하는 것은 비효율적이다.

깊이우선탐색을 하므로 모든 경우를 끝까지 돌려봐야 하기 때문이다.

또한, 백트래킹도 사용해야 하므로 bank에서 염기서열의 제거와 삽입을 반복해야 할 것이다.

따라서 DFS보다 BFS를 사용하여 해결하는 것이 수월하다.

 

② 염기서열을 end와 비교하는 작업은 큐에서 꺼내자마자 해야 한다.

start와 end가 같은 경우가 발생할 수 있기 때문이다.

만약 비교 작업을 새로운 문자열을 만든 이후에 진행하면 즉시 리턴할 수 없으므로 제대로 카운팅되지 않을 것이다.

---

4. 구현 코드

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        queue = collections.deque([[start, 0]])
        while queue:
            tmp, cnt = queue.popleft()
            if tmp == end:  # 임시 문자열과 end를 비교
                return cnt
            
            for s in 'ACGT':       # outer loop : 새로운 염기서열 선택
                for i in range(8): # inner loop : 문자열 슬라이싱 위치
                    gene = tmp[0:i] + s + tmp[i + 1:]  # 새로운 염기서열 결합

                    if gene in bank:
                        bank.remove(gene)
                        queue.append([gene, cnt + 1])

        return -1  # end를 만들 수 없는 경우

문제를 보자마자 BFS를 떠올렸지만, visit을 어떻게 처리해야 할지 고민했던 문제이다.

맨날 True/False 혹은 0/1로 값만 바꿔줬지, remove()를 사용하는 문제는 오랜만 :P