출처: https://programmers.co.kr/learn/courses/30/lessons/43163
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0를 return 합니다.
예제 #1문제에 나온 예와 같습니다.
예제 #2target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.
ㅎ.. 이 문제 겁나 이상하다.
일단 공개된 테스트케이스랑 채점테스트케이스 기준이 다르다. 이것 때문에도 겁나 삽질했다.
공개된 테스트케이스는 단어가 변환한 횟수, 채점 테스트케이스는 단어의 수라고 생각하면 된다. 이거 잘못된지 엄청 오래된 거 같은데 플머스는 고치려는 생각이 전혀 없나보다 ㅋㅋㅋㅋㅎ
여튼..
나의 알고리즘은,
먼저 begin, words에 있는 단어에 대한 딕셔너리를 만들고, value에 그 단어가 변화할 수 있는 모든 단어의 리스트를 넣어준다.
그리고 bfs로 돌면서, queue를 업데이트 할때마다 queue를 리스트로 변환해서 count에 이중리스트로 넣는다. (depth를 계산하기 위함)
모든 노드를 다 돌면 count를 돌면서 target이 있는지 찾아보고, 있으면, 그 depth에서 +1 해서 리턴한다.
없으면 0
from collections import deque
def checkWord(begin, target):
count = 0
for i in range(len(begin)):
if begin[i] != target[i]:
count += 1
if count > 1:
return False
return True
def bfs(graph, root, target):
visited = []
count = []
queue = deque([root])
while queue:
n = queue.popleft()
if n not in visited:
visited.append(n)
# if n is None, Runtime error
if n in graph:
queue.extend(list(set(graph[n]) - set(visited)))
# count depth
count.append(list(queue))
for i in range(len(count)):
if target in count[i]:
return i + 1
return 0
def solution(begin, target, words):
answer = 0
if target not in words:
return 0
graph = {}
graph[begin] = []
#init graph
for i in words:
if checkWord(begin, i):
graph[begin].append(i)
for j in words:
if i != j and checkWord(i, j):
if i not in graph.keys():
graph[i] = []
if j not in graph.keys():
graph[j] = []
graph[i].append(j)
answer = bfs(graph, begin, target)
return answerqueue extend하는 부분에서 계속 runtime error가 나서 엄청 헤맸다. graph[n]만 접근하면 에러가 나는겨.. 오늘 너무너무 피곤해서 바로 못찾은거같다;; 출근하고 밥먹고 회의하고 알고 하나 풀고 자려고 푼건데 문제도 맛이 갔고 나도 맛이 가버렸다;
이게 왜 에러 났나면, 이 words들이 서로 돌고 돌아서 나중에 차집합하고나면 빈 list가 extend되어서 n 자체가 빈 queue가 되게 된다.
그러면 pop 해봤자 None이고 그 None을 key로 딕셔너리에 접근하려고 하니까 안되지.. 아....
이거때문에 테스트케이스 4번 계에에에속 런타임 에러가 났다...
오래 삽질했지만 요즘 알고에 재미붙여서 피곤해도 재밌다. 영어 공부도 재미 좀 붙으면 좋겠다.