[level 3] Title: 단어 변환 파이썬

 

 

DFS/BFS 유형문제로 나는 BFS를 사용하여 풀어보았다. BFS구현을 위해 deque를 사용하였다.

 

처음에는 입출력이 이해가 되질 않았다. 왜 "dot"을 거치는지 이해가 되질 않았는데 (사실 아직도 이해되지않는다..) 다른 블로그들을 참고하여, 문제를 풀기위한 방법으로 이해한 것은 한 번에 "한 개의 알파벳만 바꿀 수 있다" = "한개씩만 바꿀 수 있는경우 바꿔야한다." 라고 이해했다. 그리고 이 조건은 check 함수를 만들어서 조건으로 확인하였다.

 

queue에 들어가는 값은 단어와 변환횟수(cnt)를 담았고, 결국 target과  start가 일치 할 때, 현재 cnt에 + 1 을 반환하였다.

 

 

from collections import deque

def check(word, target):
    cnt = 0
    for a, b in zip(word, target):
        if a != b:
            cnt += 1
    return True if cnt == 1 else False

def solution(begin, target, words):
    if target not in words:
        return 0
    
    w = len(words)
    visited = [0] * w
    queue = deque([[begin, 0]])

    while queue:
        start, cnt = queue.popleft()
        for i in range(w):
            if check(words[i], start) and not visited[i]:
                if words[i] == target:
                    return cnt + 1
                visited[i] = 1
                queue.append([words[i], cnt + 1])
	return 0

 

코딩테스트 연습 - 단어 변환