[프로그래머스 고득점 Kit -DFS/BFS] 단어변환

https://school.programmers.co.kr/learn/courses/30/lessons/43163

 

from collections import deque
# 1개의 알파벳만 다른 단어가 있는 경우
def diff_check(s,t):
    length = len(s)
    count = 0
    for i in range(length):
        if s[i] == t[i]:
            count += 1
    if count == length -1:
        return True
    else:
        return False

def solution(begin, target, words):
    answer = 0
    # words 안에 target 없으면 바로 return
    if target not in words:
        return answer
    # visited 리스트 만들어야 함.
    w = len(words)
    visited = [-1] * w
    q = deque()
    q.append((begin,0))
    while q:
        now,depth = q.popleft()
        if now == target:
            return depth
        # answer += 1
        for i in range(w):
            # 해당 단어를 아직 방문하지 않았고, 1개빼고 같은 경우
            if visited[i] == -1 and diff_check(now, words[i]):
                q.append((words[i],depth+1))
                visited[i] = 1
    return answer

 

이 문제는 좀 특이하다고 생각했던 게, begin 단어가 word에 있지 않아 visited 배열로 index를 저장하는 것이 살짝 모호했다. 전역 변수로 두고 visited 배열을 처리할 수도 있겠으나, 왠지 그렇게 풀기 싫었다. (네? 네...)

 

그래서 애초에 queue에 넣을 때 depth value를 넣어서 처리를 해주는 방법을 공부할 수 있었다.