[Leetcode] 433. Minimum Genetic Mutation - JS

https://leetcode.com/problems/snakes-and-ladders/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
유전자 문자열은 'A', 'C', 'G' 및 'T' 중에서 선택할 수 있는 8자의 긴 문자열로 표시될 수 있습니다.

유전자 문자열 startGene에서 유전자 문자열 endGene으로의 돌연변이를 조사해야 한다고 가정합니다. 여기서 하나의 돌연변이는 유전자 문자열에서 변경된 단일 문자로 정의됩니다.

예를 들어 "AACCGGTT" --> "AACCGGTA"는 하나의 돌연변이입니다.
유효한 유전자 돌연변이를 모두 기록하는 유전자 은행도 있습니다.
유효한 유전자 스트링이 되려면 유전자가 은행에 있어야 합니다.

두 개의 유전자 문자열 startGene 및 endGene과 유전자 은행이 주어지면 
startGene에서 endGene으로 돌연변이를 일으키는 데 필요한 최소 돌연변이 수를 반환합니다.
그러한 돌연변이가 없으면 -1을 반환합니다.

시작점은 유효한 것으로 가정하므로 뱅크에 포함되지 않을 수도 있습니다.

제한조건
--------------------
- 0 <= bank.length <= 10
- startGene.length == endGene.length == bank[i].length == 8
- startGene, endGene, and bank[i]는 ['A', 'C', 'G', 'T']로 구성된다.

 

2. 접근 방법

접근방법
--------------------
startGene 문자열을 하나씩 변경해서 endGene으로 만들 수 있는 최소 횟수가 필요하다.
단, bank에 포함된 문자열로만 변경이 가능하다.

queue안에 [현재 문자열, 돌연변이 횟수]를 담는다.
현재 문자열을 첫번째 요소부터 'G', 'A', 'T', 'C' 와 비교하여 해당 요소만 바꿔서 새로운 문자열을 만든다.

새로운 문자열이 방문했던 문자열이 아니고 bank에 포함되어 있다면 queue에 추가한다.
만약 현재 문자열이 endGene과 같다면, 그 때의 돌연변이 횟수를 반환한다.
BFS 탐색이 완료되어도 못구했다면 -1 반환

 

 

3. 코드

/**
 * @param {string} startGene
 * @param {string} endGene
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function(startGene, endGene, bank) {
    const bankSet = new Set(bank);
    if (!bankSet.has(endGene)) return -1

    const genes = ['G','A','T','C'];

    const queue = [[startGene,0]];
    const visited = new Set([startGene]);

    while (queue.length) {
        const [currentGene, mutations] = queue.shift();

        if (currentGene === endGene) return mutations;

        for (let i = 0; i < currentGene.length; i++) {
            for (let gene of genes) {
                if (gene !== currentGene[i]) {
                    const mutated = currentGene.slice(0,i) + gene + currentGene.slice(i+1);

                    if (!visited.has(mutated) && bankSet.has(mutated)) {
                        visited.add(mutated);
                        queue.push([mutated, mutations+1]);
                    }
                }
            }
        }
    }
    return -1
};

 

 

4. 복잡도 분석

- 시간복잡도: O(N*L*4), N은 유전자 문자열 길이(8), L은 bank 길이, 4는 유전자 종류

- 공간복잡도: O(L)

 

1회 변경된 돌연변이 문자열과 돌연변이 횟수를 배열로 queue에 추가하는 방식이 Snakes and Ladders 문제와 비슷했다.

문자열을 돌연변이화 할 때, 'G', 'A', 'C', 'T' 중에서 변경해줘야하는 경우의 수를 추가해줘야 하여 시간 복잡도가 4가 추가되었다.

최단 경로 문제는 BFS 탐색으로 접근하는 방법을 생각해봐야겠다.