[프로그래머스] 단어변환 (Lv.3) - (BFS/DFS)

처음 나의 풀이 (동작은 됨)

from collections import deque

def solution(begin, target, words):

    visited = [False] * len(words)

    queue = deque()

    for word in words:  # 후보 단어 삽입

        diff = 0

        for idx in range(len(word)):

            if begin[idx] != word[idx]:

                diff += 1

        if diff == 1:

            queue.append((word, 1))

            visited[words.index(word)] = True

    while queue:

        cur, cnt = queue.popleft()

        if cur == target:

            return cnt

        for word in words:

            if not visited[words.index(word)]:

                diff = 0

                for idx in range(len(word)):

                    if cur[idx] != word[idx]:

                        diff += 1

                if diff == 1:

                    queue.append((word, cnt + 1))

                    visited[words.index(word)] = True

    return 0

 

문제점..

❌ 함수 분리 미흡	글자 차이 체크 로직이 중복
❌ index() 사용	words.index(word)는 중복 단어가 있을 경우 버그 발생 가능성 + 시간 복잡도 ↑
❌ 가독성 낮음	반복되는 코드가 많아 유지보수 어려움

 

 

개선된 코드 (리팩토링 완료)

from collections import deque

def is_one_letter_diff(a, b):

    diff = 0

    for ch1, ch2 in zip(a, b):

        if ch1 != ch2:

            diff += 1

    return True if diff == 1 else False

def solution(begin, target, words):

    visited = [False] * len(words)

    queue = deque()

    for idx, word in enumerate(words): #후보단어 큐에 삽입

        if is_one_letter_diff(begin, word):

            queue.append((word, 1))

            visited[idx] = True

    while queue:

        cur, cnt = queue.popleft()

        if cur == target:

            return cnt

        for idx, word in enumerate(words):

            if is_one_letter_diff(cur, word) and not visited[idx] :

                queue.append((word, cnt+1))

                visited[idx] = True

    return 0

 

개선 포인트

함수 분리	is_one_letter_diff() 함수로 차이 비교 로직 추출 → 가독성 향상
enumerate() 사용	인덱스를 안전하게 가져와 index() 비효율 제거
간결한 리턴문	return diff == 1 형태로 불필요한 삼항 연산 제거