[Programmers] 단어 변환

태환·2024년 3월 24일
0

Coding Test

목록 보기
144/151

📌 [Programmers] 단어 변환

📖 문제

📖 예제

📖 풀이

from collections import deque

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

def BFS(begin, target, words):
    queue = deque()
    queue.append((begin, 0))
    while queue:
        now, step = queue.popleft()
        
        if now == target:
            return step
        
        for word in words:
            cnt = 0
            for i in range(len(now)):
                if now[i] != word[i]:
                    cnt += 1
            if cnt == 1:
                queue.append((word, step+1))

target 단어가 words에 없을 경우 0을 리턴한다.
target 단어가 words에 있을 경우 BFS를 활용하여 문제를 해결할 수 있다.
begin이 target까지 도달하는 최단거리를 구하는 문제이다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글