programmers 단어 변환(DFS/BFS)

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

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

 

위 문제는 begin단어가 target단어까지 몇번만에 변화를 하는지 확인하는 문제이다.

 

나의경우

bfs를 이용하여 풀었는데 begin단어가 변할 수 있는 words를 확인하기 위해 모든 단어들을 list형태로 다시 풀어주었고,

다른알파벳이 하나인 경우에만  begin단어를 변환시켜 target단어까지 가는데 count를 세어주었다.

 

---

def solution(begin, target, words):
    begin = list(begin) # 단어를 알파벳 단위로 확인하기 위해 list로 바꾸어줌
    target = list(target) # 위와동일
    for i in range(len(words)): # 위와동일
        words[i] = list(words[i])

    def bfs(begin, answer):
        q = []
        q.append((begin, answer))

        while q:
            nowbegin, nowanswer = q.pop(0)

            if nowbegin == target:
                return nowanswer

            if target not in words: #단어가 target으로 변하지 못하는 경우 0을 return 시켜주는 if문
                return 0

            for y in range(len(words)):
                cnt = 0
                for x in range(len(words[y])):
                    if nowbegin[x] != words[y][x]:
                        cnt += 1
                if cnt == 1:
                    q.append((words[y], nowanswer + 1))


    answer = bfs(begin,0)
    return answer