프로그래머스 코딩테스트 고득점 Kit_DFS/BFS_단어변환

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

변환가능한 단어를 인접한 노드로 생각하여 인접리스트형태로 그래프를 생성한다.

인접한 노드인지 아닌지 판별하는 방법:
=> 전체 중 1개의 문자가 다름
=> 이때, 다른 문자의 위치가 똑같아야한다는 점에 주의한다
=> ex) hhf 와 hkh는 1개의 문자가 다르지만 다른 문제 f와k의 위치가 다르기 때문에 변환가능하지 않다.

이동횟수를 카운트 하며 BFS순회한다.
target을 만날 경우, 이동횟수를 return하고 종료한다.
만약 target을 만나지않고 BFS순회를 끝마친다면 target을 만나지 못한것이므로 0을 return하고 종료한다.

구현 코드👇

from collections import defaultdict

def solution(begin, target, words):
    
    words.append(begin) #그래프 만들기 위해 시작점 begin단어 추가
    n = len(words) 
    
    #그래프 생성 (한개의 알파벳만 다를경우 =  인접)
    #주의할 점: 다른 알파벳의 위치가 같아야함 ( (ex) 'min'과 'mnk'는 인접하지X)
    graph = defaultdict(list)
    for i in range(n-1):
        before = words[i]
        for j in range(i+1, n):
            after = words[j]
            df_cnt = 0
            for bf, af in zip(words[i], words[j]):
                if bf != af:
                    df_cnt += 1
                    if df_cnt > 1:
                        break
            if df_cnt == 1:
                graph[before].append(after)
                graph[after].append(before)
    
    #BFS
    visited = []
    q = [(begin, 0)]  #[(node, 거리)]
    while q:
        node, cnt = q.pop()
        if node == target: 
            return cnt
        if node not in visited:
            visited.append(node)
            for v in graph[node]:
                q.append((v, cnt + 1))
    return 0