[알고리즘] 프로그래머스 | 단어변환

단어 변환

답: 

온전히 함수로 분리해 풀이하기

from collections import deque

def bfs(begin, target, words):
    q = deque()
    q.append((begin, 0))
    
    while q:
        start_word, step = q.popleft()
        
        if start_word == target:
            return step
        for word in words:
            count = 0
            for i in range(len(word)):
                if word[i] != start_word[i]:
                    count += 1
            
            if count == 1:
                q.append((word, step+1))

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

 

 

문제 분석 및 해석

 

 

>> 풀이생각

bfs / dfs 문제

차근차근 스텝을 생각해보자.

 

1. 바꿀 영어단어target이 words에 있는지 확인 ->없으면 0

 

2. 주어진 영어단어 begin을 기준으로 1자리씩 바꾸어나가는 방법..을 사용해야할 것 같은데, bfs/ dfs로 어떻게 구현하는가?

- '최소'니까 bfs를 사용하기

- queue에 begin과 step(현재 변환 상태) 함께 담아 시작하기

 

- 변환 가능한 단어가 words에 있는지 확인하기

- 변환한 후 cnt +1면 단어를 바꾸어 queue에 넣어주기, count 넣기? -> count 는 무조건 1, step을 넣되 +1을 해주어야함

- 동일하면 return 

 

 

 

리뷰.

단계별로 나누어 풀이할 수 있도록 계속 연습 중이다.

 

풀이 방법은 어떻게든 생각할 수 있는데 여전히 구현 능력이 부족하게 느껴진다ㅠ,ㅠ
더 많이 풀이하자..