[프로그래머스] 단어 변환(LV.3) by javascript - 깊이/너비 우선 탐색(DFS/BFS)

▷ 문제 : 깊이/너비 우선 탐색(DFS/BFS) - 단어 변환 LV.3

코딩테스트 연습 - 단어 변환

▷ 해결 날짜 : 2022.04.08
▷ 소요 시간 : 1시간 30분
▷ 풀이 과정 :

일단 문제는 그래프 탐색 알고리즘을 사용해서 풀면 된다.

두 개의 단어 begin, target과 단어의 집합 words가 주어지는데, 아래에 주어진 두 규칙을 이용해 가장 짧은 변환 과정을 찾으면 된다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

그래서 우선 두 단어의 각 위치별로 비교해서 하나만 다른지 체크해주는 함수를 만들었고, 최소 횟수를 찾기 위해 큐에 [문자열, 횟수]를 넣어서 계속해서 탐색을 하는 방식으로 구현하였다.

 

처음에는 인접리스트나 인접 행렬같이 그래프를 만들어야 하는데 어떻게 만들지 라는 고민 때문에 시간이 많이 소요되었고, 결론은 그냥 딱히 필요 없겠구나 싶어 방향을 잡고 구현하게 되었다.

 

▷ 구현

function solution(begin, target, words) {
    const visited = [];
    const queue = [[begin, 0]];

    while(queue.length){
        let [w, c] = queue.shift();
        if(w === target) return c;

        words.forEach(word => {
            if(!visited.includes(word)){
                if(checked(w, word)){
                    queue.push([word, ++c]);
                    visited.push(word);
                }
            }
        });
    }

    return 0;
}

function checked(str1, str2){
    let check = 0;
    for(let i = 0; i < str1.length ; i++){
        if(str1[i] !== str2[i]) check++;
    }
    return check === 1;
}

▷ 복기 :
찾아보면 뭐 대충 어떤 경우의 수를 구한다거나, 이동 과정에서 제약이 있다거나 등등 이럴때 DFS를 쓰고

최단거리 또는 최소횟수, 미로 탐색 같은 거에 BFS를 사용한다는데 결론은 그냥 문제 많이 풀면 감이 잡힌다고들 한다.

 

지금은 그냥 대체로 BFS 사용해서 풀고는 있는데 막히면 잘 모르겠다... (내가 사용하는 게 BFS 인지도 모르겠다 혼란하다 혼란해)