🥚문제

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

• DFS/BFS

---

🥚입력/출력

---

🍳코드

from collections import deque

def solution(begin, target, words):
    visited = [False]*len(words)

    q = deque([(begin, 0)])
    while q:
        current, change_cnt = q.popleft()
        if current == target:
            return change_cnt

        for i in range(len(words)):
            if diff(current, words[i]) == 1 and not visited[i]:
                q.append((words[i], change_cnt + 1))
                visited[i] = True
    return 0


def diff(word1, word2):
    cnt = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            cnt += 1
    return cnt

---

🧂아이디어

BFS

• 큰 어려움 없이 BFS로 풀이할 수 있었던 문제

• words[i]가 current와 글자 수 차이가 1이고, words[i]를 아직 방문한 적이 없다면 q에 words[i]와, 글자 변환 횟수인 change_cnt + 1을 삽입한다. q.append(words[i], change_cnt + 1)

• current == target일 경우 지금까지의 change_cnt를 반환한다.

• begin을 target으로 변환하지 못하는 경우 0을 반환한다.