문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=python3
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
문제 풀이
핵심 아이디어
1. 한 글자만 다른 단어인지 확인하는 함수
def is_one_diff(word1, word2):
diff = sum([w1 != w2 for w1, w2 in zip(word1, word2)])
return diff == 1
2. BFS(너비 우선 탐색) 으로 변환 단계를 탐색 (최소 단계니까 BFS가 적합)
3. 방문한 단어는 다시 방문하지 않기
최종 코드
from collections import deque
def solution(begin, target, words):
if target not in words:
return 0
visited = set()
queue = deque([(begin, 0)]) # (현재 단어, 변환 횟수)
while queue:
current, steps = queue.popleft()
if current == target:
return steps
for word in words:
if word not in visited and is_one_diff(current, word):
visited.add(word)
queue.append((word, steps + 1))
return 0 # 끝까지 못찾으면
def is_one_diff(word1, word2):
diff = sum([w1 != w2 for w1, w2 in zip(word1, word2)])
return diff == 1
'코딩테스트' 카테고리의 다른 글
[프로그래머스] [python] 리코쳇 로봇 (0) | 2025.07.06 |
---|---|
[프로그래머스] [Java] JadenCase 문자열 만들기 (0) | 2025.07.01 |
[프로그래머스] [Java] 표 편집 (0) | 2025.06.26 |
[프로그래머스] [Java] 부대복귀 (1) | 2025.06.23 |
[코딩테스트] 코딩테스트 대비 Java 문법 벼락치기 정리 (1) | 2025.05.19 |