[Programmers] 단어 변환

사용 언어: Python3

문제

단어 변환

풀이

BFS

from collections import deque

def solution(begin, target, words):
    answer = 0
    q = deque()
    q.append([begin, 0])
    visited = [0 for _ in range(len(words))]
    
    if target not in words:
        return 0
    
    while q:
        word, cnt = q.popleft()
        if word == target:
            answer = cnt
            break
        for i in range(len(words)):
            temp_cnt = 0
            if not visited[i]:
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        temp_cnt += 1
                if temp_cnt == 1: # 한 글자만 다른 경우
                    q.append([words[i], cnt+1]) # 큐에 넣기
                    visited[i] = 1
    
    return answer

두 번째

from collections import deque
def solution(begin, target, words):
    answer = 10000
    q = deque()
    visited = [0 for _ in range(len(words))]
    
    q.append([begin, 0])
    
    if target not in words:
        return 0
    
    while q:
        word, cnt = q.popleft()
        if word == target:
            answer = min(answer, cnt) # ✅ min() 사용
            break
        for i in range(len(words)):
            tmp = 0
            if not visited[i]:
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        tmp += 1
                if tmp == 1:
                    q.append([words[i], cnt+1])
                    visited[i] = 1
    
    return answer

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기