프로그래밍/기타
[프로그래머스][Python3] 단어 변환
snoopybox
2019. 11. 22. 01:31
문제 :
https://programmers.co.kr/learn/courses/30/lessons/43163
나의 풀이 :
from collections import deque
def solution(begin, target, words):
def is_only_one_diff(a, b):
remain = 1
for i in range(len(a)):
if a[i] != b[i]:
remain -= 1
if remain < 0:
return False
return remain == 0
queue = deque([(begin, 0)])
visited = set()
while queue:
curr, depth = queue.popleft()
if curr == target:
return depth
visited.add(curr)
for word in words:
if is_only_one_diff(curr, word) and word not in visited:
queue.append((word, depth+1))
return 0
나의 풀이2 :
deque를 사용하지 않는 버전
def solution(begin, target, words):
def is_only_one_diff(a, b):
remain = 1
for i in range(len(a)):
if a[i] != b[i]:
remain -= 1
if remain < 0:
return False
return remain == 0
queue = [begin]
depth = 0
visited = set()
while queue:
next_queue = set()
for curr in queue:
if curr == target:
return depth
visited.add(curr)
for word in words:
if word not in visited and is_only_one_diff(curr, word):
next_queue.add(word)
queue = next_queue
depth += 1
return 0