Programmers_43163 단어 변환

• TOC {:toc}

이 글은 프로그래머스의 43163번 문제를 자바스크립트(JavaScript)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2024.01.09

function canConverted(begin, target) {
    let count = 0;
    [...begin].forEach((c, i) => {
        count += Number(c !== target[i]);
    });

    return count === 1;
}

function solution(begin, target, words) {
    // initialize connection
    const nextWord = Array.from(new Array(words.length), () => []);

    for (let i = 0; i < words.length; i += 1) {
        for (let j = i; j < words.length; j += 1) {
            if (i === j) continue;
            if (canConverted(words[i], words[j])) {
                nextWord[i].push(j);
                nextWord[j].push(i);
            }
        }
    }

    // bfs
    const queue = [];
    const used = Array(words.length).fill(false);

    words.forEach((word, i) => {
        if (canConverted(begin, word)) queue.push([i, 1]);
    });

    while (queue.length) {
        const [now, count] = queue.shift();
        if (words[now] === target) return count;

        used[now] = true;
        nextWord[now].forEach((next) => {
            if (!used[next]) {
                queue.push([next, count + 1]);
            }
        });
    }

    return 0;
}

아이디어 & 풀이

begin에서 출발해 count를 증가시켜가며 다음 단어를 탐색하고, 해당 단어가 target과 같으면 count를 반환한다.

• BFS를 이용해 연결된 단어 중 근접한 단어부터 탐색해야 ‘가장 짧은’ 변환 수를 구할 수 있다.
• 각 단어를 하나의 노드라고 할 때 현재 단어에서 다음 단어로 변환할 수 있으면 두 노드가 연결된 상태로 볼 수 있다.

우선 연결된 노드의 목록을 구성한다.

• 보다 간결한 비교를 위해 연결된 노드의 목록을 구성하는 데에는 각 단어의 ‘인덱스 값’을 사용한다.
• 입출력 예시 1번을 예로 들면 다음과 같다.
  • words배열: ["hot", "dot", "dog", "lot", "log", "cog"]
  • words중 0번째 단어인 hot에서 변환될 수 있는 단어는 dot과 lot이므로 노드의 목록 배열의 0번째 원소는 [1, 3]이다.
  • 결과적으로 연결된 노드의 목록 배열은 다음과 같이 구성할 수 있다.
    • [[ 1, 3 ], [ 0, 2, 3 ], [ 1, 4, 5 ], [ 0, 1, 4 ], [ 2, 3, 5 ], [ 2, 4 ]]
• 두 단어를 인자로 받은 뒤 변환 조건을 만족하는지 여부를 boolean으로 반환하는 canConverted 함수를 별도로 작성해 연결된 노드 목록을 구성한다.

BFS는 queue를 이용해 구현한다.

• queue의 원소는 다음 단어의 인덱스 값과 현재 count 값의 배열 [i, count]로 구성한다.
• queue에서 꺼낸 현재 단어가 target과 같은지 확인한 뒤
  • 같으면 바로 count를 반환하고
  • 같지 않으면 다음 연결된 단어를 순회하며 해당 단어의 인덱스 값과 현재 count에서 1 증가시킨 값을 queue에 집어넣는다.
• 이미 확인한 단어를 재확인하는 일을 막기 위해 used 배열을 생성해 사용 여부를 표기한다.