from collections import deque
import re
def solution(begin, target, words):
answer = 0
queue = deque([[begin, 0]])
visited = {begin:1}
while queue :
temp, n = queue.popleft()
if temp == target : return n
for i in range(len(temp)) :
a = temp[:i] + "." + temp[i+1:]
p = re.compile(a)
for j in words :
if j not in visited and p.match(j) :
visited[j] = 1
queue.append([j, n+1])
return answer
문제정리
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
위의 두개의 조건을 통해 begin단어에서 target단어까지 변환하는데 걸린 횟수를 리턴
바꿀 수 없을 때에는 0 리턴
즉, begin: hit → target: cog일때
hit → hot → dog → cog 3번 변환으로 리턴
풀이과정
문제에서 bfs/dfs를 보긴하였지만 조건중 한 번에 한개의 알파벳만 변경을 보고 그래프 탐색을 통해 풀이해야겠다고 생각하였다.
저번에 길찾기 문제처럼 최단 거리(변환)을 풀이할때 bfs의 특성을 이용하여 단어에 해당하는 노드들을 탐색하여 풀이하여야 겠다고 생각하였다.
다만 문제는 한번에 한개의 알파벳만 바꿀 수 있는 조건을 맞추는거에 대하여 조건을
한개 말고 나머지 알파벳들이 같을 경우 해당 단어로 바꿀 수 있다라고 생각하였다
즉 hit일때 it가 같은 것을 찾아야한다고 생각하여 조건이 까다롭다고 생각하였다.
즉 10글자일경우 한글자를 제외한 나머지 9글자를 비교하여 9글자가 같은 조건을 추가해야겠다고 생각하였고 너무 조건이 까다로워 무조건 re를 써야한다고 생각하여 그렇게 풀이하였다.
a = temp[:i] + "." + temp[i+1:]와 같이 매번 re 조건을 만들어 풀이하였는데
re의 .연산자는 “a.b”일경우 asb, aeb, aqb등 .인 문자를 제외하고 같은 문자를 찾는 연산자이다 이를 이용하여 풀이하였다. 해당하는 문자일 경우 queue에 넣어 bfs를 하도록하였다.
최소카운트는 queue에 넣을때 횟수도 같이 input하여 풀이하였다.
풀이 후
위에서 까다롭다고 계속 설명한 한개 말고 나머지 알파벳들이 같을 경우 해당 단어로 바꿀 수 있다라고 생각하였다 이렇게 생각하여 어려웠다.
문자열을 반복하여 틀린 경우를 세고 틀린 경우가 1개일 경우 변환가능하다고 풀이하였다.
특히 제너레이터를 이용한 풀이가 있었는데 기억이 남아 아래에 적어놓는다.
from collections import deque
def get_adjacent(current, words):
for word in words:
if len(current) != len(word):
continue
count = 0
for c, w in zip(current, word):
if c != w:
count += 1
if count == 1:
yield word
def solution(begin, target, words):
dist = {begin: 0}
queue = deque([begin])
while queue:
current = queue.popleft()
for next_word in get_adjacent(current, words):
if next_word not in dist:
dist[next_word] = dist[current] + 1
queue.append(next_word)
return dist.get(target, 0)
제너레이터를 이용하여 정말 깔끔하다고 생각하게 풀이하였고 zip을 통해 로직이 엄청 깔끔해 보였다.
제너레이터의 이해도가 정말 높으며 적절히 사용된 사례라고 생각한다.
배울점이 많은 코드라고 생각한다.