프로그래머스 | dfs/bfs | 단어변환

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

프로그래머스

 

2026.04.01

zip 함수 사용이 여전히 미숙했고,,

bfs 자체 구현은 나쁘지 않게 했다. visited가 집합이 될 수 있다는건 몰랐지만

(bfs는 1. queue 구현 2. visited 정의 3. while 4. popleft 5. 종료조건 6. 인접한 노드 7. 조건 만족하면 queue에 넣고 방문처리)

from collections import deque
# 한 단어만 다른지 체크하는 함수
def validate(w1, w2):
#     if w1 == w2:
#         return False
    
#     diff = 0
#     for i in range(len(w1)):
#         if w1[i] != w2[i]: # 한 단어씩 비교하기
#             diff += 1
#             if diff > 1: # 이미 두 단어 이상이 다르면 더 돌지 말고 끝내기
#                 break
#     return (diff == 1)
    return sum(a != b for a, b in zip(w1,w2)) == 1

# 시작 단어로부터 갈 수 있는 다른 단어 찾기
def curr_to_next(curr,words):
    next_list = []
    for i in range(len(words)):
        if validate(curr, words[i]):
            next_list.append(words[i])
    return next_list

def bfs(begin,target,words):
    queue = deque([(begin,0)])
    visited = set()
    
    while queue:
        word, cnt = queue.popleft()
        # 종료 조건
        if word == target:
            return cnt
        
        for next_word in curr_to_next(word, words):
            if next_word not in visited: # 사용했던 단어가 아니면
                queue.append((next_word,cnt+1))
                visited.add(next_word) # 방문처리
    
    return 0 # 2. 중간 연결 다리가 없을 때
    
    
def solution(begin,target,words):
    # begin -> target으로의 최단거리
    # 변환할 수 없을 때는 0을 return
        # 1. words 안에 taget이 없을 때
        # 2. 중간 연결 다리가 없을 때
    # [구현 방법]
        # begin 단어로부터 갈 수 있는 모든 경로로 가야 함 (bfs)
        # 그 중에 종료조건이 target이랑 같을 때 멈추는 것
        
    if target not in words:
        return 0 # 1. words 안에 taget이 없을 때
    
    return bfs(begin,target,words)

 

 

 

---

from collections import deque
def near_words(a, b):
    different = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            different += 1
    if different == 1:
        return True
    else:
        return False
    
def make_graph(graph, begin, words):
    for i in range(len(words)):
        if near_words(begin, words[i]):
            graph[0].append(i+1)
            
    for i in range(len(words)):
        for j in range(i+1, len(words)):
            if near_words(words[i], words[j]):
                graph[i+1].append(j+1);graph[j+1].append(i+1)
                
def bfs(graph, begin_idx, target_idx, visited):
    queue = deque()
    queue.append((begin_idx,0))
    visited[begin_idx] = True
    while queue:
        v, cnt = queue.popleft()
        if v == target_idx:
            return cnt
        for next_v in graph[v]:
            if not visited[next_v]:
                queue.append((next_v, cnt+1))
                visited[next_v] = True
    return 0

def solution(begin, target, words):
    if target not in words:
        return 0
    
    graph = [[] for _ in range(len(words)+1)]
    make_graph(graph, begin, words)
    visited = [False] * (len(words)+1)
    
    answer = bfs(graph, 0, words.index(target)+1, visited)
    return answer

 

복잡하게 푼 이유 
(1) zip 함수를 까먹음
(2) idx처리 방법밖에 몰라서 그래프 순회하려고 했는데, 집합 이용하면 쉽게 해결될 문제였음

 

from collections import deque
def near_words(a, b):
    diff = sum(1 for x,y in zip(a,b) if x!=y)
    return diff == 1

def solution(begin, target, words):
    if target not in words:
        return 0
    
    queue = deque([(begin,0)])
    visited = set()
    
    while queue:
        word, cnt = queue.popleft()
        if word == target:
            return cnt
        for next_word in words:
            if next_word not in visited and near_words(word,next_word):
                queue.append((next_word,cnt+1))
                visited.add(next_word)