[Python/파이썬] 단어 변환 (BFS) (프로그래머스 코딩테스트 고득점 Kit)

 

 

 

<풀이>

from collections import deque


def solution(begin, target, words):
    answer = 0
    wordsNum = len(words)
    visited = [0 for _ in range(wordsNum)]

    queue = deque()
    queue.append(begin)
    while queue:
        popWord = queue.popleft()
        if popWord == target:
            answer = visited[words.index(target)]
            break
        for i in range(wordsNum):
            if visited[i] == 0:  # 아직 방문하지 않은 단어만 방문함
                check = 0
                for j in range(len(popWord)):
                    if popWord[j] != words[i][j]:
                        check += 1
                if check == 1:  # 단어 비교를 했을 때 한 알파벳만 다른 경우
                    if popWord == begin:  # 첫 단어에서 시작한 경우
                        visited[i] = 1
                    else:
                        visited[i] = visited[words.index(popWord)] + 1
                    queue.append(words[i])


    return answer

하나의 알파벳만 다른 것을 어떻게 체크할까 했는데 위와 같이 해결할 수 있음을 알게되었다.

 

 

 

<핵심 정리>

1. visited는 dictionary로도 구현할 수 있다.

2. 문자열에서 한 문자만 다른 걸 체크할 땐 replace 함수를 이용하기보다 위와 같이 for문으로 비교해서 체크하는 것이 좋다.