문제
https://school.programmers.co.kr/learn/courses/30/lessons/43163
BFS로 간단하게 풀어보자!
주요 아이디어
- 가장 짧은 변환 과정 -> 최단 경로 -> BFS를 떠올려야 한다
- begin을 queue에 넣고 시작
- 하나씩 popleft() 하면서 순회
- visited에 방문 처리
- 한 글자가 다른 단어로만 변환 가능하므로, 인접 노드는 한 글자만 다른 것들 넣기
- 최단 경로이므로 target과 가장 가까운 순서대로 pop해야 함
- 변환 안될 경우 0을 반환해서 예외처리 해주기
코드 구현 (Python 3)
더보기
from collections import deque
# 단어 2개가 몇 개 알파벳 일치하는지 개수 반환
def word_check(word, now):
cnt = 0
for idx in range(len(word)):
if word[idx] == now[idx]:
cnt += 1
return cnt
def solution(begin, target, words):
answer = -1
visited = []
queue = deque()
queue.append(begin)
while queue:
# 뽑기 전에 sort 해야 함
# target이랑 가장 가까운 순서로 돌아야 하므로, target과 글자 차이 가장 적은 순으로 정렬
queue = deque(sorted(queue, key=lambda x: word_check(x, target), reverse=True))
now = queue.popleft()
visited.append(now) # 방문 처리
answer += 1 # path append
if now == target:
break
# 알파벳 현재꺼랑 하나만 다른 것들 & 방문 안한 것들
adj = [x for x in words if word_check(x, now) == len(now)-1 and x not in visited]
for adj_word in adj:
if adj_word not in queue:
queue.append(adj_word)
# 모두 방문했음에도 target으로의 변환이 불가능한 경우
if now != target:
return 0
else:
return answer
제출 결과
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 문자열 다루기 기본 (0) | 2024.05.21 |
---|---|
[프로그래머스] 가장 먼 노드 (0) | 2024.05.21 |
[프로그래머스] 행렬 테두리 회전하기 (0) | 2024.04.11 |
[프로그래머스] 등굣길 (0) | 2024.04.08 |
[프로그래머스] 조이스틱 (0) | 2024.04.07 |