433. Minimum Genetic Mutation

433. Minimum Genetic Mutation

 

이 문제는 그래프 탐색 문제로 생각할 수 있습니다.

각각의 유효한 유전자 문자열(gene)을 노드로 보고,

한 번의 변이로 연결될 수 있는 두 노드를 간선으로 연결하여

최단 경로를 찾는 방식으로 해결합니다.

---

문제의 주요 포인트

1. 유전자 변이의 정의:
   • 두 유전자 문자열에서 단 하나의 문자만 다른 경우, 한 번의 변이라고 간주합니다.
   • 예: "AACCGGTT" → "AACCGGTA" (1개의 문자만 변이).
2. 유효한 변이 조건:
   • 변이 후의 문자열은 반드시 bank에 포함되어 있어야 합니다. 그렇지 않으면 유효하지 않은 변이로 간주합니다.
3. 목표:
   • startGene에서 endGene까지 변이를 통해 도달하기 위해 필요한 최소 변이 횟수를 계산합니다.
   • 도달할 수 없는 경우 -1을 반환합니다.
4. 제약 조건:
   • 유전자 길이는 항상 8입니다.
   • bank에 최대 10개의 유전자가 포함될 수 있으므로 문제를 효율적으로 해결할 수 있습니다.

---

접근 방법

이 문제는 그래프에서 최단 경로를 찾는 문제와 유사하므로 **BFS (Breadth-First Search)**를 사용하면 적합합니다.

BFS 알고리즘

1. 그래프 모델링:
   • 각 유전자 문자열을 노드로 간주.
   • 한 번의 변이로 연결 가능한 노드들 간에 간선을 생성.
2. 탐색 구조:
   • 큐를 사용하여 BFS를 수행.
   • queue에 현재 유전자와 변이 횟수를 함께 저장: (currentGene, mutationCount).
3. 종료 조건:
   • currentGene가 endGene에 도달하면, mutationCount를 반환.
4. 추가 고려사항:
   • 이미 방문한 노드를 다시 탐색하지 않도록 visited 집합을 유지.
   • 변이가 유효하려면, 변이 후의 유전자가 반드시 bank에 포함되어야 합니다.

from collections import deque

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
        # 유효하지 않은 endGene인 경우
        if endGene not in bank:
            return -1

        # BFS 탐색 준비
        queue = deque([(startGene, 0)])  # (현재 유전자, 변이 횟수)
        visited = set([startGene])  # startGene을 바로 방문 처리
        valid_chars = ['A', 'C', 'G', 'T']  # 가능한 문자 집합

        while queue:
            current, mutations = queue.popleft()

            # 종료 조건: endGene에 도달
            if current == endGene:
                return mutations

            # 현재 유전자로부터 가능한 변이를 생성
            for i in range(len(current)):
                for char in valid_chars:
                    # 한 글자만 변경
                    mutated = current[:i] + char + current[i+1:]
                    # 유효한 변이인지 확인
                    if mutated in bank and mutated not in visited:
                        queue.append((mutated, mutations + 1))
                        visited.add(mutated)  # 바로 방문 처리

        # BFS 종료 후 도달할 수 없는 경우
        return -1

 

코드 설명

1. 유효성 검사:
   • endGene가 bank에 없는 경우,
   • 변이를 통해 도달할 수 없으므로
   • 바로 -1 반환.
2. BFS 탐색:
   • queue에서 현재 유전자와 변이 횟수를 가져옵니다.
   • 한 번에 한 문자를 변이하여 가능한 모든 새로운 유전자를 생성합니다.
   • 유효한 변이(bank에 포함되고 아직 방문하지 않은 유전자`)인 경우 큐에 추가합니다.
3. 종료 조건:
   • currentGene == endGene인 경우, 현재 변이 횟수를 반환.
4. 방문 처리:
   • 변이된 유전자는 중복 방문하지 않도록 visited 집합에 추가합니다.