[python] 프로그래머스_단어변환 (DFS&BFS)

문제

 

풀이

BFS 로 풀 수 있고, 현재 단어와 words 중에 단어 하나만 다른 경우에 해당 words 를 방문하고 카운트해준다. 그렇게 반복하다가 현재 단어가 target 단어와 같아 지는 순간 BFS 종료하고 카운트한 수를 리턴해준다.

 

코드

def bfs(begin, target, words, visited):
    count = 0
    stack = [(begin, 0)]
    while stack:
        cur, depth = stack.pop()
        if cur == target:   # target에 도달했으면 depth 리턴
            return depth
        
        for i in range(len(words)):
            if visited[i] == True:  # 이미 지나쳤던 words 이면 패스
                continue
            cnt = 0
            for a,b in zip(cur, words[i]):
                if a!=b: # 다른 단어가 있는 경우 cnt +=1
                    cnt += 1
            if cnt == 1: # 단어가 하나만 다를 때, 해당 words 방문하고 stack에 단어와, depth +1
                visited[i] = True
                stack.append((words[i], depth+1))
                

def solution(begin, target, words):
    answer = 0
    if target not in words:
        return 0

    visited = [False]*(len(words))

    answer = bfs(begin, target, words, visited)

    return