본문 바로가기

알고리즘/프로그래머스(Python)

bfs - 단어 변환 / 파이썬

from collections import deque

def ck(w1, w2):
    cnt = 0
    lenth = len(w1)
    for i in range(lenth):
        if w1[i] == w2[i]: cnt += 1
    return True if cnt == lenth-1 else False

def solution(begin, target, words):
    if target not in words:
        return 0
    q = deque()
    for w in words:
        if ck(begin, w):
            q.append([w, 1])
    while q:
        word, cnt = q.popleft()
        if word == target:
            return cnt
        for w in words:
            if ck(word, w):
                q.append([w, cnt+1])
    return 0

 

 

programmers.co.kr/learn/courses/30/lessons/43163

 

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

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수

programmers.co.kr