[프로그래머스] lv3. 단어 변환 풀이 (TypeScript)

프로그래머스

접근한 방법

DFS로 현재 문자열에서 한 글자씩 지워가며 비교하는 방식으로 탐색합니다. 

예를 들어 begin이 hit라면, 순차적으로 *it, h*t, hi* 과 같은 위치인 글자가 words배열에도 존재하는지 확인하여 존재하면 진입 횟수를 카운트하여 재탐색합니다. 이때 이미 방문했던 단어들은 제외하기 위해 방문 배열을 설정하여 관리합니다.

 

target이 발견되면 현재까지 저장했던 result 카운트를 갱신한 후 DFS가 완전히 끝날 때 남아있는 result의 값이 최소 비교 횟수가 됩니다.

 

코드 설명

1. visited 배열은 방문한 단어를 표시하기 위한 배열로, 모든 요소를 0으로 초기화합니다. 방문한 단어를 표시하는 것으로 해당 단어가 이미 선택되었음을 나타냅니다. 

2. result 변수는 최소 변환 횟수를 저장합니다. 초기에 큰 값(여기서는 50)으로 설정합니다.

3. dfs는 깊이 우선 탐색을 수행하는 재귀 함수입니다. 현재 단어(now)와 현재까지의 변환 횟수(cnt)를 인자로 받습니다.

- 현재 단어가 목표 단어인 경우(now === target) 최소 변환 횟수(result)를 갱신합니다.

- 현재 단어에서 한 문자씩 바꿔가며 words 배열 내의 다른 단어와 비교합니다. 문자열을 두 부분으로 나누어, 왼쪽 부분(l)과 오른쪽 부분(r)을 비교합니다.

- words 배열 내의 단어들과 비교하면서, 한 문자만 다른 단어를 찾고 이전에 방문한 적이 없는 경우(!visited[j])에 해당 단어를 선택하여 재귀적으로 호출합니다.

- 선택한 단어를 방문한 것으로 표시하고(visited[j] = 1) 호출을 마친 후에는 다시 방문하지 않았음을 나타내기 위해 방문 표시를 원래대로 되돌립니다(visited[j] = 0).

4. result 값이 여전히 초기값인 50인 경우, 시작 단어에서 목표 단어로 변환하는 경로가 없는 것으로 간주하고 0을 반환합니다. 그렇지 않으면 최소 변환 횟수인 result를 반환합니다.

 

TypeScript

function 단어변환(begin: string, target: string, words: Array<string>) {
  const visited = Array(words.length).fill(0);

  let result = 50;
  const dfs = (now: string, cnt: number) => {
    if (now === target) return (result = Math.min(result, cnt));

    for (let i = 0; i < now.length; i += 1) {
      const [l, r] = [now.slice(0, i), now.slice(i + 1, now.length)];
      for (let j = 0; j < words.length; j += 1) {
        const [wl, wr] = [
          words[j].slice(0, i),
          words[j].slice(i + 1, words[j].length),
        ];
        if (l + r === wl + wr && !visited[j]) {
          visited[j] = 1;
          dfs(words[j], cnt + 1);
          visited[j] = 0;
        }
      }
    }
  };
  dfs(begin, 0);
  if (result === 50) return 0;
  return result;
}
console.log(단어변환("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]));

 

* 겨우 5개의 테스트케이스로 코드를 정답이라 확신하기에는 무리가 있지 않나 싶네요. 테스트케이스 추가 후 재채점이 필요해보입니다.