[프로그래머스/Python] Level 3_단어 변환(DFS)

📌문제 유형

BFS, DFS

 

📌문제

프로그래머스

 

📌나의 문제풀이

- DFS 이용

- 최소 몇 단계의 과정 -> dfs 밑에 use.remove()로 제거하고 진행하기 (이거 안하면 계속 쌓이기만 함)

def dfs(now, words, use, answer, target, res):
    if answer > len(words):
        return 0
    
    if now == target:
        if res[0] > answer:
            res[0] = answer
            return 
    
    for x in range(len(words)):
        d = 0
        for y in range(len(words[x])):
            if words[x] not in use:
                if words[x][y] != now[y]:
                    d += 1
        if d == 1:
            if words[x] not in use:
                use.append(now) # 현재 사용한 단어 넣기
                dfs(words[x], words, use, answer + 1, target, res)
                use.remove(now) # 현재 사용한 단어 빼기

def solution(begin, target, words):
    answer = 0
    result = len(words)
    res = [len(words)]
    
    if target not in words:
        return 0
    
    for i in range(len(words)):
        diff = 0
        for j in range(len(words[i])):
            if words[i][j] != begin[j]:
                diff += 1
        if diff == 1:
            dfs(words[i], words, [], 1, target, res)
            if result > res[0]:
                result = res[0]
    
    return result

 

 

📌다른사람의 문제풀이

- BFS 활용

from collections import deque

def get_adjacent(current, words):
    for word in words:
        if len(current) != len(word):
            continue

        count = 0
        for c, w in zip(current, word):
            if c != w:
                count += 1

        if count == 1:
            yield word


def solution(begin, target, words):
    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()

        for next_word in get_adjacent(current, words):
            if next_word not in dist:
                dist[next_word] = dist[current] + 1
                queue.append(next_word)

    return dist.get(target, 0)

 

파이썬의 yield 키워드와 제너레이터(generator)

 

210924 개발기록: 파이썬 dictionary, get()을 사용해야하는 이유

 

📌리뷰

- DFS에 대한 개념 제대로 알아가기

• dfs는 리프노드까지 탐색 -> dfs 함수 다음 코드 실행하며 return 
• dfs 뒤 use.remove는 노드 올라오면서 하나씩 지우는 것! => 최소값 찾기 가능