https://school.programmers.co.kr/learn/courses/30/lessons/43163#qna
언뜻보면 브루트 포스로 해결할 수 있을 것 같은 문제지만, 한가지 함정이 존재한다.
만약 hit에서 hot으로 넘어가고, hot에서 dot으로 넘어간다. 그럼 또 dot에서 hot으로 넘어갈 경우가 생기니 무한루프에 빠지게 된다.
결국 우리는 이미 순회했던 단어를 제외할 필요가 있다.
보통 테스트 케이스 3번에서 실패가 많이들 나온다.
우선 처음 제출했던 코드이다.
from collections import deque
def solution(begin, target, words):
# 아이디어
# bfs로 풀어야함
# visit처리는 큐에 들어갈 배열을 제외한 새 배열을 할당
if target not in words:
return 0
q = deque()
q.append([begin,0])
while q:
s,cnt = q.popleft()
if s == target:
return cnt
# s = list(s.strip())
new_words = words
for word in words:
in_cnt = 0
for w in word:
if w not in s:
in_cnt += 1
if in_cnt == 1:
q.append([word,cnt + 1])
new_words.remove(word)
words = new_words
return 0
전체적인 흐름은 맞지만 내가 작성한 방식은 단순히 어떤 문자가 s라는 문자열 안에 존재하는지만 판단한다.
나는 좀 더 자세하게 인덱스까지 확인해야 할 필요성을 느꼈다.
begin = "aab"
target = "aba"
words = ["abb", "aba"]
위 테스트 케이스로 실험했고, 아래는 성공이 된 수정 코드이다.
from collections import deque
from copy import deepcopy
def solution(begin, target, words):
# 아이디어
# bfs로 풀어야함
# visit처리는 큐에 들어갈 배열을 제외한 새 배열을 할당
if target not in words:
return 0
q = deque()
q.append([begin, 0])
while q:
s, cnt = q.popleft()
if s == target:
return cnt
# s = list(s.strip())
new_words = deepcopy(words)
for i in range(len(words)):
isnt_same_cnt = 0
for j in range(len(words[0])):
if s[j] != words[i][j]:
isnt_same_cnt += 1
# return
if isnt_same_cnt == 1:
q.append([words[i], cnt + 1])
new_words.remove(words[i])
words = new_words
return 0