[DFS/BFS] 단어 변환 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

[문제 간단 요약]

 

• 시작 단어(begin)를 목표 단어(target)으로 변환
• 변환 규칙:
  1. 한 번에 한 글자만 바꿀 수 있음
  2. 변환된 단어는 반드시 주어진 단어 목록(words)에 포함
• begin에서 target으로 변환하는 최소 단계 수를 반환
• 변환이 불가능한 경우 0 반환

 

 

[문제 해결 방안]

• 그래프 탐색 문제: 각 단어를 노드로 보고, 한 글자 차이 나는 단어끼리 연결
• DFS 또는 BFS로 탐색 가능
  • DFS: 모든 경로 탐색 후 최소 단계 갱신
  • BFS: 최단 경로 탐색에 더 직관적
• 본 풀이는 DFS로 구현

 

[문제 해결 코드 - python]

def chk_rule(pre_word, post_word):
    cnt = 0
    for i in range(len(pre_word)):
        if pre_word[i] != post_word[i]:
            cnt += 1
    return cnt == 1

def dfs(begin, target, cnt, words):
    global result, used
    if begin == target:
        result = min(result, cnt)
        return
    
    for idx in range(len(words)):
        if chk_rule(begin, words[idx]) and used[idx] == 0:
            used[idx] = 1
            dfs(words[idx], target, cnt+1, words)
            used[idx] = 0
    return

def solution(begin, target, words):
    global result, used
    result = float('inf')
    used = [0]*len(words)
    dfs(begin, target, 0, words)
    return result if result != float('inf') else 0

 

[코드 개선점]

• 비교 함수 최적화
  두 단어의 차이가 2 이상이면 즉시 중단 → 성능 개선
• 전역 변수 제거
  Python에서는 global result, used 대신 함수 인자로 넘겨주면 가독성 ↑
• DFS → BFS 대체 가능
  최단 거리 문제이므로 BFS를 사용하면 더 직관적으로 해결 가능
• 복잡도 분석
  • 단어 수: 최대 50
  • 각 단어 길이: 최대 10
  • 단어 비교 O(L), 전체 탐색 O(N²L) (N=단어 개수, L=단어 길이)
  • 제한 범위 내에서 충분히 빠름

[코드 개선점 참고 문제 해결 코드 - javascript]

function chkRule(a, b) {
  let diff = 0;
  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      diff++;
      if (diff > 1) return false;
    }
  }
  return diff === 1;
}

function solution(begin, target, words) {
  const visited = new Array(words.length).fill(false);
  const queue = [[begin, 0]];
  
  while (queue.length > 0) {
    const [word, cnt] = queue.shift();
    if (word === target) return cnt;
    
    for (let i = 0; i < words.length; i++) {
      if (!visited[i] && chkRule(word, words[i])) {
        visited[i] = true;
        queue.push([words[i], cnt + 1]);
      }
    }
  }
  return 0;
}