[프로그래머스][LV.3] 단어 변환 | python3

문제링크:  단어 변환

---

문제설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한조건

- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0를 return 합니다.

---

 

문제풀이

아이디어를 참고하여 혼자 풀어봤다.

코드 짜기 전에는 단어가 한글자만 다른지 어떻게 비교해? 라고 생각했는데

코드를 짜면서 보니 걍 간단하게 해결 가능한 거였음

 

여기서 visited가 루트마다 리셋되어야 하는거 아닌가? 하고 이해가 안됐는데

지금은 이해가 된다.

 

어차피 최단거리를 찾는 것이기 때문에 먼저 그 단어에 도착했다면 나중에 그 단어에 도착하는 루트는 최단 거리가 아님.

visited를 활용하여 더 효율적으로 탐색할 수 있다.

 

그리고 BFS 문제에서는 pop() 이 아니라 popleft() 로 쓰는 게 좋다. 먼저 dq에 들어간 요소를 처리해야 하기 때문.

pop()을 사용하면 DFS처럼 동작할 수 있다고 함.

 

 

♣ popleft()

👉 FIFO(선입선출) 구조가 유지됨 → 올바른 BFS

 

♣ pop()

👉 최근에 추가된 단어부터 처리됨
👉 즉, 스택(LIFO)처럼 동작할 가능성이 높음
👉 DFS처럼 깊이 우선 탐색이 될 위험이 있음

 

 

🔹 BFS와 DFS의 차이점

✅ BFS (너비 우선 탐색, Queue 사용)

• 가까운 노드(= 먼저 변환된 단어)부터 탐색
• Queue(FIFO, 선입선출) 구조를 사용 → popleft()
• 최단 경로를 찾기에 적합
• 탐색 순서:

  시작 → 1단계 → 2단계 → 3단계 → ...
  

  즉, 한 단계씩 진행하면서 너비(= 레벨)를 늘려감.

✅ DFS (깊이 우선 탐색, Stack 사용)

• 한 경로를 끝까지 탐색한 후, 다시 돌아와서 다른 경로 탐색
• Stack(LIFO, 후입선출) 구조를 사용 → pop()
• 한 번에 깊이 들어가기 때문에 최단 경로 보장이 안 됨
• 탐색 순서:

  시작 → 한 방향으로 끝까지 → 백트래킹(다른 길로 탐색)
  

  즉, 한 방향으로 깊이 들어가다가 막히면 되돌아가서 다른 길을 탐색.

---

🔹 BFS vs DFS 예제

📌 단어 변환 예제

begin = "hit"
target = "cog"
words = ["hot", "dot", "dog", "lot", "log", "cog"]

✅ BFS (Queue + popleft())

dq = deque(["hit"])  

탐색 순서:

hit  →  hot  →  dot  →  dog  →  cog  (최단 경로!)
          └→  lot  →  log

👉 한 단계씩 탐색하면서 최단 경로 보장됨 ✅

---

❌ DFS처럼 동작하는 경우 (Stack + pop())

dq = deque(["hit"])  

탐색 순서:

hit  →  hot  →  dot  →  dog  →  log  (한 방향으로 깊게 탐색)
                           └→  cog  (너무 늦게 찾음)

👉 먼저 들어온 요소가 늦게 꺼내지면서 비효율적인 탐색이 될 수 있음 ❌
👉 최단 경로 보장이 안 됨!

---

🔹 왜 스택처럼 동작하면 DFS가 될까?

DFS는 후입선출(LIFO) 방식의 스택을 사용해서
👉 최근에 추가된 노드를 먼저 꺼내 탐색함.

✨ pop()을 사용하면 어떻게 될까?

w, cnt = dq.pop()  # 오른쪽(뒤쪽)에서 꺼냄

• 가장 나중에 추가된 요소부터 꺼내기 때문에 한쪽 방향으로 깊이 들어가게 됨
• 즉, BFS의 레벨 탐색 구조가 깨지고, 깊이 우선 탐색(DFS)처럼 동작하게 됨!

🚨 결론: pop()을 사용하면 DFS처럼 동작할 가능성이 크다! 
👉 따라서 BFS에서는 popleft()를 써야 한다! 

 

 

나의코드

from collections import deque

def solution(begin, target, words):
    
    if target not in words:
        return 0
    
    answer = 0
    dq=deque([(begin,0)])
    visited=[False]*len(words)
    
    while dq:
        w,cnt=dq.pop()
        
        for idx,word in enumerate(words): # visited를 활용하기 위해 idx가 필요
            chk=0
            if visited[idx]: # 방문한 적 있으면..근데 루트마다 방문전적이 리셋되어야 하지 않나? # 최단거리라서 상관 없음
                continue
            for n,m in zip(w,word):
                if n != m:
                    chk+=1
                    
            # word가 target과 같으면 종료해야함. 바뀌고 난 후에 종료.. 
            # 생각해보니 dq에 넣기 전에 종료해도 될 듯.
            # 아니다. chk가 1일때만 가능하니 그 밑에 있어야 겠다
            
            
            if chk==1:
                if word==target:
                    return cnt+1
                dq.append((word,cnt+1))

 

---

 

참고하기

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])  # BFS 큐 초기화

    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)  # target까지 변환할 수 없으면 0 반환

 

---

📌 dict.get(key, default)의 동작 원리

• **dict.get(key, default)**는 key가 존재하면 그 값을 반환, 없으면 default 값을 반환하는 함수야.
• 즉, target이 dist에 있으면 변환 횟수를 반환하고, 없으면 기본값(0)을 반환함.

 

---

🔹 제너레이터(Generator)란?

**제너레이터(generator)**는 **이터레이터(iterator)**의 한 종류로, 데이터를 한 번에 하나씩 반환하는 함수야.
yield 키워드를 사용해서 값을 반환하며, 일반적인 함수와 다르게 한 번 호출될 때마다 실행이 멈췄다가 다시 실행될 수 있어.

---

✅ 제너레이터 vs 일반 함수

📌 1. 일반 함수 (return) 사용 예시

def get_numbers():
    return [1, 2, 3, 4, 5]

print(get_numbers())  # [1, 2, 3, 4, 5]

• 한 번에 모든 값을 리스트로 반환
• 메모리를 많이 차지할 수 있음 (특히, 대량 데이터 처리 시 비효율적)

---

📌 2. 제너레이터 (yield) 사용 예시

def get_numbers():
    for i in range(1, 6):
        yield i  # 값을 하나씩 반환 (중간에 멈췄다가 다시 실행 가능)

gen = get_numbers()  # 제너레이터 객체 생성

print(next(gen))  # 1
print(next(gen))  # 2
print(next(gen))  # 3

💡 차이점:
✔ return은 함수가 한 번 실행되면 종료되지만,
✔ yield는 값을 반환한 후에도 함수의 상태를 유지하고, 필요할 때 다시 실행됨.

---

✅ 제너레이터가 좋은 이유

1️⃣ 메모리 절약

• 한 번에 모든 데이터를 메모리에 저장하지 않고 필요할 때마다 값을 생성해서 반환함.
• 예를 들어, 100만 개의 숫자를 리스트로 만들면 메모리를 많이 차지하지만, 제너레이터를 사용하면 메모리 효율적임.

def big_numbers():
    for i in range(1, 1_000_001):  # 100만 개 숫자 생성
        yield i  # 한 개씩 반환 (메모리 절약)

gen = big_numbers()
print(next(gen))  # 1
print(next(gen))  # 2

---

2️⃣ 반복 작업 최적화

• for 문에서 자동으로 next()를 호출하면서 값을 하나씩 꺼낼 수 있음.
• 끝까지 꺼내면 자동으로 StopIteration 예외 발생.

def get_letters():
    for char in "hello":
        yield char

for letter in get_letters():  # next()를 자동으로 호출
    print(letter)

# 출력:
# h
# e
# l
# l
# o

---

✅ 코드에서 yield를 사용한 이유

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  # 변환 가능한 단어를 하나씩 반환 (메모리 절약)

왜 yield를 썼을까?
✔ return을 쓰면 한 번에 모든 단어를 리스트로 반환해야 하지만, yield를 사용하면 한 개씩 필요한 순간에 반환할 수 있음 → 메모리 절약
✔ BFS 탐색에서 next_word가 필요할 때마다 하나씩 반환 → 불필요한 연산 줄임

---

🔹 결론

• **제너레이터(generator)**는 yield를 사용하여 값을 하나씩 반환하는 함수
• 메모리를 효율적으로 사용하고, 반복 작업을 최적화할 수 있음
• 코드에서 yield를 사용한 이유는 한 번에 모든 단어를 반환하지 않고, 필요할 때마다 한 개씩 꺼낼 수 있도록 하기 위해서!