1. 문제
https://leetcode.com/problems/minimum-genetic-mutation/
Minimum Genetic Mutation - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
2. 리뷰
아주 재밌는 문제다.
처음에는 백트래킹으로 풀었고, 최적화를 통해 꽤 괜찮은 결과를 냈다.
그런데 문제가 요구하는 바를 잘 살펴보면, BFS가 더 적합하고 효율적임을 알 수 있었다.
백트래킹, BFS, DFS 등은 모두 완전탐색 기반의 알고리즘이다.
하지만 각 알고리즘의 특징을 잘 이해하고 있다면, 각 문제에 더 적합한 알고리즘을 적용할 수 있다.
BFS는 그래프를 배타적으로 최단거리 완전탐색하는 알고리즘이다.
- 그래프
그래프라고 하면 동그란 노드들과 노드를 잇는 간선이 떠오른다.
맞는 말이기는 한데, 항상 그렇게 그래프가 시각적으로 주어지는 것은 아니다.
그래프는 오히려 논리적인 개념으로써 현실 세계를 적당히 추상화하여 그래프화 할 수 있다.
그래프의 노드는 어떠한 상태를 가리킬 수 있고, 간선은 상태 간의 연관성을 가리킨다. - 배타적
visited 배열을 사용하는 BFS는 배타적이다.
노드를 방문할 때마다 visited 배열을 체크함으로써, 같은 노드를 두 번 방문하지 않기 때문이다.
그런데 필요에 따라서 visited 배열을 사용하지 않을 수도 있다. 그럴 경우 BFS 알고리즘은 동일 노드를 두번 이상 방문할 수도 있다. - 최단거리
BFS가 DFS와 가장 다른 특징 중 하나일 것이다.
최단거리, 최소 변화, 최소 움직임 등 최솟값을 묻는 문제에 BFS가 유용하게 쓰일 수 있다.
일단 목적지에 방문하였다면, 그 순간이 곧 최단거리이기 때문이다 - 완전탐색
BFS는 모든 노드를 다 탐색하는 완전탐색 기반의 알고리즘이다.
3. 백트래킹 풀이
문자열로 상태가 주어져서, 딱 보고 그래프가 떠오르지 않았다.
그래서 그냥 모든 경우의 수를 다 따져보자는 생각에 백트래킹을 적용했다.
아무래도 백트래킹이 재귀호출을 이용하는 완전탐색 알고리즘이다보니 처음에는 효율이 좋지 못했다.
그런데 적절히 조건을 걸어 최적화를 하니, 백트래킹으로도 꽤 준수한 결과가 나왔다.
백트래킹 최적화
- 최소 횟수로 변환이 이루어졌을 경우, 모든 재귀호출을 종료한다.
예를 들어start = 'AACCTTGG', end='ATCGTTGG일 경우, 최소한 2개의 문자(두번째, 네번째)를 바꿔야 한다.
따라서 만약 최소한의 횟수로 변환이 성공적으로 이루어졌다면, 더 이상 백트래킹을 진행할 필요 없이, 최소 횟수가 답이 된다. - 반드시 변환해야하는 인덱스의 문자열부터 변환하자.
앞선 예시를 재활용해서start = 'AACCTTGG', end='ATCGTTGG일 경우, (두번째, 네번째)문자열이 바뀌어야 한다. 따라서 앞 문자부터 순서대로 변환하며 탐색하는 것이 아니라, 두번째와 네번째 문자를 먼저 바꾸면서 탐색을 하자는 전략이다.
이러한 전략이 반드시 시간효율을 낮춘다는 보장은 없다. 그러나 직관적으로 생각해보면 이러한 탐색이 유의미할 것임을 짐작할 수 있다.
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
# 1. backtracking
ref = {'A': ('C', 'G', 'T',), 'C': ('A', 'G', 'T',), 'G': ('A', 'C', 'T',), 'T': ('A', 'C', 'G',)}
def backtracking(string, cnt):
nonlocal mn
# 종료조건
if string == end:
mn = min(mn, cnt)
return
# 가지치기
if cnt >= mn:
return
if mn == MIN: # 최적화 기법 1. 최소한의 횟수로 변환이 성공했을 시, 모든 재귀호출 종료
return
# 재귀호출
for idx in nodes: # 최적화 기법 2. 만들어둔 nodes 배열을 이용하여 반드시 변환해야하는 문자열부터 변환
for c in ref[string[idx]]:
middle = string[:idx] + c + string[idx+1:]
if bank.get(middle):
bank[middle] = False
backtracking(middle, cnt + 1)
# 최적화 작업. 없을 경우 33ms -> 59ms
different = [] # 반드시 변환해야 하는 문자열의 인덱스 저장
same = [] # 반드시 변환할 필요없는 문자열의 인덱스 저장
MIN = 0 # 최소한의 변환 횟수를 계산하는 변수
for i in range(8):
if start[i] != end[i]:
MIN += 1
different.append(i)
continue
same.append(i)
nodes = different + same # 변환해야 하는 문자열 인덱스가 앞에 오도록 함으로써, BFS 탐색 시 해당 문자열부터 변환시킴
bank = {gene: True for gene in bank}
mn = 9
backtracking(start, 0)
# 프린트
if mn == 9:
return -1
else:
return mn4. BFS 풀이
문자열로 주어졌지만 우리는 다음과 같이 논리적인 그래프를 생각할 수 있다.
start 문자열이 시작노드, end 문자열이 종료 노드, 그리고 bank에 있는 문자열들이 중간 노드들이다.
그리고 어떤 문자열에서 한 개의 문자를 바꿔서 다른 문자열이 만들어진다면, 그 두 노드는 연결되어 있다.
즉, 이 문제는 시작노드로부터 종료노드까지 최단거리를 구하는 전형적인 BFS문제이다.
재밌는 점은 단순히 BFS를 이용했다고 처음부터 시간효율이 좋지는 않았다.
다음에 방문할 노드의 유효성을 검증하는 if문을 적절히 최적화 해준 뒤에야 비로소 최고효율이 나왔다.
BFS 최적화
변환시킨 문자열의 존재여부, 그리고 존재한다면 방문여부를 체크하는 조건을 하나의 if문으로 구현하였다.
- 먼저 bank에 존재하는 문자열을 key로 하는 딕셔너리를 만든다. 초기 value는 True이다.
visited = {gene: True for gene in bank}문자열에 순서가 정해져있지 않기 때문에 기존의 리스트 visited배열을 만들기 어려웠고, 무엇보다 딕셔너리로 구현하면 검색하는 시간복잡도 O(1)이라는 장점이 있다. 초기 value를 True로 한 이유는 다음에 설명한다. if visited.get['문자열']
위의 if문으로 문자열의 존재여부와 방문여부를 한 번에 확인할 수 있다.
먼저 문자열이 존재하지 않으면 null이라는 Falsy값이 반환된다.
그리고 문자열이 존재하여도 방문하였다면 False가 반환된다.(방문 시에 True를 False로 변환해줌)
오직 문자열이 존재하고 방문하지 않았을 경우에만 처음에 셋팅해준 True가 반환되어 조건문이 실행된다.
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
# 2-2. BFS with Boolean ref
ref = {'A': ('C', 'G', 'T',), 'C': ('A', 'G', 'T',), 'G': ('A', 'C', 'T',), 'T': ('A', 'C', 'G',)}
def bfs(start):
visited = {gene: True for gene in bank} # bank에 저장된 문자열을 key로 하는 딕셔너리 형성. 초기 value는 True
q = deque()
q.append((start, 0))
while q:
string, cnt = q.popleft()
if string == end:
return cnt
for idx in range(8):
for c in ref[string[idx]]:
middle = string[:idx] + c + string[idx+1:]
if visited.get(middle): # 문자열이 없으면 None, 이미 방문했으면 False, 문자열이 존재하고 방문하지 않았을 경우에만 True 반환
visited[middle] = False # 해당 문자열방문 처리
q.append((middle, cnt+1))
return 9
mn = bfs(start)
if mn == 9:
return -1
else:
return mn