문제를 정리해보자.
시작단어, 목표단어, words가 주어진다. 시작단어를 목표단어가 되도록 변환해야 한다.
아래와 같은 규칙으로 단어를 변환할 수 있다.
시작단어가 목표단어가 되기 위해 몇 단계가 필요한가?
프로그래머스에 있는 예를 보자.
시작단어 : "hit"
목표단어 : "cog"
words : ["hot","dot","dog","lot","log","cog"]
"hit" -> "hot" -> "dot" -> "dog" -> "cog" 이렇게 4단계가 필요하다.
풀이를 생각해보자.
위의 예에서, 자리 별로 바꿀 수 있는 알파벳을 생각해보자.
첫 번째 : h, d, l, c
두 번째 : o
세 번째 : t, g
변환해보자.
지금단어 : hit
첫 번째 변환 : hit, dit, lit, cit,
두 번째 변환 : hot
세 번째 변환 : hit, hig
즉, hit 단어는 총 7번 변환할 수 있다.
그런데 변환된 hot단어만 words안에 있는 단어이다.
때문에 지금단어를 hot단어로 바꾸고 또 변환한다.
변환해봤던 단어는 다시 변환하지 않는다.
만약 다시 변환이 가능하게 된다면 무한루프에 빠져서, 목표단어를 만들 수 없는 경우를 잡을 수 없다.
구현해보자.
BFS로 구현했다.
from collections import deque
def solution(begin, target, words):
# 입력
l = len(words[0]) # 단어 길이
alpha = [[] for _ in range(l)] # 자리 별 알파벳 모음
words_li = {} # 변경 가능한 단어
target_li = list(target) # 목표단어
for i in range(l):
dp = [0] * 26
for word in words:
words_li[str(list(word))] = 1
# {"['h', 'o', 't']": 1, "['d', 'o', 't']": 1, "['d', 'o', 'g']": 1,
# "['l', 'o', 't']": 1, "['l', 'o', 'g']": 1, "['c', 'o', 'g']": 1}
if dp[ord(word[i]) - 97] == 0:
dp[ord(word[i]) - 97] = 1
alpha[i].append(word[i]) # [['h', 'd', 'l', 'c'], ['o'], ['t', 'g']]
# BFS 구현
queue = deque([[list(begin), 0]]) # [단어, 트리 깊이]
check = {str(list(begin)): 1} # 이미 시도해 본 단어
while queue:
string = queue.popleft()
for i in range(l):
for j in range(len(alpha[i])):
tmp_string = [s for s in string[0]] # 단어 복사 (주소값 문제로 인해)
tmp_string[i] = alpha[i][j] # 단어 변경
if not check.get(str(tmp_string), 0) and words_li.get(str(tmp_string), 0):
if tmp_string == target_li:
return string[1] + 1
else:
queue.append([tmp_string, string[1] + 1])
check[str(tmp_string)] = 1
return 0
print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
'변환했던 단어는 다시 변환하지 않는다.' 이 부분을 if 현재단어 in [변환했던 단어들] 로 확인하는 게 싫었다. (계속 O(N)이 걸리니까.)
그래서 문자열과 딕셔너리를 이용했다.,
딕셔너리의 key 값으로, 단어 리스트를 문자열로 변환해서 넣었다. 그리고 value값을 1로 바꿨다.
이제 key값에 해당하는 value 값이 1일 경우 변환했던 단어임을 알 수 있다.
몇 단계인지 구해야 하는데, 이것은 트리의 깊이로 구했다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스][Python] 등굣길 (2) | 2022.01.13 |
---|---|
[프로그래머스][Python] 정수 삼각형 (0) | 2022.01.13 |
[프로그래머스][Python] 네트워크 (0) | 2022.01.11 |
[프로그래머스][Python] 타겟 넘버 (0) | 2022.01.11 |
[프로그래머스][Python] 징검다리 (0) | 2022.01.05 |