[DFS/BFS] 단어 변환

문제 설명

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

프로그래머스

문제 풀이

• begin 에 담긴 단어를 알파벳 하나씩 바꿔가며 target에 담긴 단어로 변환하는 과정
• 규칙은 words 리스트에 담긴 단어들로만 변환 할 수 있음.
• 딕셔너리를 이용해서 풀 수도 있겠지만 그냥 인덱스로 계산해서 코드를 짬
• begin이 변할 수 있는 것들도 찾기 위해 일단 words에 담음
• words에 담긴 각각의 단어들에 대해 자신이 변할 수 있는 모든 경로를 찾아서 그래프에 담음
• 이후 begin(0번째 인덱스)을 큐에 담아서 BFS 탐색을 진행
• next가 end(words에 담긴 target읜 인덱스) 와 같다면 cnt+1 을 리턴 해줌
• while문이 끝났는데도 리턴 값이 없다면 존재하지 않는 경우이므로 0 

소스 코드

from collections import deque

def solution(begin, target, words):
    if(target not in words):
        return 0
    words=[begin]+words	 #begin으로부터 변환 할 수 있는 것들을 찾기 위해 words에 넣어줌
    end = words.index(target)
    n = len(words)
    k=len(begin)
    visited=[False]*n
    gr = [[]for i in range(n)]
    for i in range(n):		#각각의 단어들로부터 변환 할 수 있는 쌍들을 찾는 과정
        cur = words[i]
        for j in range(i+1,n):
            next = words[j]
            dif = 0
            for z in range(k):
                if cur[z]!=next[z]:
                    dif+=1
                if dif>=2:
                    break
            if dif==1:
                gr[i].append(j)
                gr[j].append(i)
    
    q=deque()
    q.append((0,0))
    visited[0]=True
    while(q):	//BFS
        cur,cnt = q.popleft()
        for next in gr[cur]:
            if visited[next]==True:
                continue
            if next==end:
                return cnt+1
            visited[next]=True
            q.appendleft((next,cnt+1))
    return 0

print(solution("hit","cog",["hot", "dot", "dog", "lot", "log", "cog"]))