단어 변환

Eunseo·2022년 7월 20일
0

Programmers

목록 보기
8/9
post-thumbnail

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

✅ Problem Summary

두 개의 단어 begin, target과 단어의 집합 words가 주어질 때, begintarget으로 변환하는 최소 단계 수를 구하는 문제

  • 한 번에 한 개의 알파벳만 바꿀 수 있음
  • words에 있는 단어로만 변환할 수 있음
  • 모든 단어의 길이는 같으며, 중복되는 단어는 없음
  • 변환할 수 없는 경우에는 0를 return

🧮 Applied Theory & Algorithm

1. 너비 우선 탐색 (Breadth-First Search)

그림 출처: Wikipedia


📑 My Answer

  • 모든 테스트 케이스 통과
from collections import deque
def solution(begin, target, words):
    if target not in words:
        return 0

    queue = deque([(0, begin)])
    while queue:
        depth, tempWord = queue.popleft()
        if tempWord == target:
            return depth

        for w in words:
            diffChar = 0
            for i in range(len(w)):
                if tempWord[i] != w[i]:
                    diffChar += 1
            if diffChar == 1:
                queue.append((depth + 1, w))
    return 0

📌 코드 구현 설명

  • 현재 단어 tempWordtarget 단어와 같은지 확인한다.
  • 만약 tempWordtarget 단어와 같지 않다면 word에서 바꿀 수 있는 문자를 탐색한다.
    • 한 번에 한 문자만 바꿀 수 있기 때문에, tempWord에서 하나의 문자만 다른 문자를 찾는다.
  • tempWordtarget와 같아질 때 까지 반복하며, 만약 바꿀 수 없다면 0return 한다.

profile
내가 공부한 것들

0개의 댓글