https://school.programmers.co.kr/learn/courses/30/lessons/43163
BFS 알고리즘을 사용해 본 문제를 구현하였다. 코드 구현 단계는 다음과 같다.
from collections import deque
def solution(begin, target, words):
answer = 0
visited = [0 for i in range(len(words))] # 단어의 개수만큼 visited 배열 생성
queue = deque()
queue.append([begin, 0]) # 시작 단어, 단어변환 횟수를 큐에 삽입
while queue:
nword, ncnt = queue.popleft()
if nword == target: # 현재 단어가 target 단어와 같다면 현재까지의 변환 횟수를 리턴
answer = ncnt
break
else: # 다르면, 한 글자만 다른 단어를 찾아야 함
for i in range(len(words)): # words 배열의 모든 단어들의 visited를 탐색
if visited[i] == 0: # 방문하지 않은 노드이면 해당 단어가 현재 단어와 몇 글자가 다른지 파악
tmp_cnt = 0
for j in range(len(nword)):
if nword[j] != words[i][j]:
tmp_cnt += 1 # 글자가 다른 자리마다 temp count 값을 1씩 추가
if tmp_cnt == 1: # 한 글자 다른 단어이면
ncnt += 1 # 변환 횟수를 증가시킴
queue.append([words[i], ncnt]) # 바꿀 단어를 큐에 삽입
visited[i] = 1 # 방문 여부를 참으로 바꿈
return answer
실행 결과
def solution(begin, target, words):
if target not in words: # target 단어가 words 배열에 없으면 0을 리턴
return 0
answer = 0
while(1):
arr = [0 for _ in range(len(words))] # words 배열과 같은 길이의 배열을 생성해서 현재 begin과 배열 안 각 단어들의 글자 수 차이를 기록함
for s in range(len(words)):
val = 0
for i in range(len(words[s])):
if begin[i] != words[s][i]:
val += 1
arr[s] = val
for i in range(len(arr)): # arr 배열에 기록한 숫자를 통해 한 자리만 다른 단어를 begin 값으로 교체
if arr[i] == 1:
begin = words[i]
answer += 1 # 교체할 때마다 교체 횟수를 1씩 증가시킴
if target == begin:
return answer
실행 결과
# 오류 발생 코드 (테스트 케이스의 값과 틀림)
def solution(begin, target, words):
if target not in words: # target 단어가 words 배열에 없으면 0을 리턴
return 0
answer = 0
while target != begin: # target 값에 도달하지 못한 경우 while문 반복
for s in words:
d = 0
for i in range(len(s)):
if begin[i] != s[i]: # begin과 s 단어의 각 자리가 같은지 비교
d += 1 # 다르면 변수에 1을 더해 기록
change = 0
if d == 1: # 한 자리만 다른 단어이면
begin = s # 단어를 바꿔줌
change += 1 # 단어를 바꾸는 경우를 기록
else:
continue
if change == 1:
answer += 1
return answer
실행 결과