[프로그래머스] 깊이/너비 우선 탐색 3. 단어 변환

문제

https://programmers.co.kr/learn/courses/30/lessons/43163?language=python3 

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

---

풀이

처음엔 dfs나 bfs나 상관 없겠거니 싶었는데 

dfs로하면 hit -> hat 대신 hit -> jit -> jat -> hat 같이 최소 단계가 아닌 개수를 반환하게 되어 bfs로 변환했다.

 

1. 반복문을 돌며 begin에서 1개만 바꿔 만들 수 있는 단어를 스택에 넣음
   몇번째 단계를 거쳤는지 count를 스텍에 튜플 형태로 함께 저장
   ex) [('hot', 1), ('hit', 1), ('hat', 2), ... ]
2. 1의 begin 대신 stack을 pop한 값으로 반복
3. target과 일치하면 count 반환stack을 모두 비웠는데도 target에 도달할 수 없으면 0 반환

 

찾아보니 bfs를 활용하면 효과적으로 풀 수 있는 문제 조건들이 있었다. (https://developer-mac.tistory.com/64)

1. 최소 비용 문제
2. 정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내에 만족한다.)
3. 간선의 가중치가 1이다.

처음엔 dfs로 풀려고 계획해서 count를 모두 저장했는데, bfs로 풀거였으면 count를 튜플형태로 저장할 필요는 없다.

def solution(begin, target, words):
    stack = [(begin, 0)]
    visited = [False for _ in words]
    
    while stack:
        now, count = stack.pop(0)
        for i in range(len(words)):
            diff = 0
            if visited[i]:
                continue
            for j in range(len(words[i])):
                if words[i][j] != now[j]:
                    diff += 1
            if diff == 1:
                if words[i] == target:
                    return count + 1
                stack.append((words[i], count + 1))
                visited[i] = True
    
    return 0

 

---

다른 사람의 풀이

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 - 제너레이터 (https://dojang.io/mod/page/view.php?id=2412) 처음 보는 문법이다.