프로그래머스 Lv3 BFS/DFS 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/43163
[나의 풀이]
⌛ 35분 소요
from collections import deque
def solution(begin, target, words):
answer = 0
if target not in words:
answer = 0
return answer
queue = deque([(begin,0)])
while queue:
now_word,cnt = queue.popleft()
if now_word == target:
answer = cnt
break
else:
queue.extend(get_queue(now_word,cnt,words))
return answer
def get_queue(now_word,cnt,words):
queue = deque([])
for word in words:
wrong = 0
can_convert = True
for idx,x in enumerate(word):
if x!=now_word[idx]:
wrong += 1
if wrong == 2:
can_convert = False
break
if can_convert:
queue.append((word,cnt+1))
return queue
입력된 시작 단어(begin)에서 최소 몇단계에 걸쳐 목표 단어(target)로 변환할 수 있는지를 계산하는 문제입니다. 이때, 한번에 한글자만 변환할 수 있기 때문에 Queue를 활용한 BFS구조를 구현하여 현재 단어에서 변할 수 있는 단어 리스트를 append하며 cnt를 세는 방식입니다. BFS 원리 그자체를 활용하면 되는 문제로 어렵지 않게 구현할 수 있었습니다.🐥🐥🐥
[다른 사람의 풀이1]
from collections import deque
def solution(begin, target, words):
answer = 0
q = deque()
q.append([begin, 0])
V = [ 0 for i in range(len(words))]
while q:
word, cnt = q.popleft()
if word == target:
answer = cnt
break
for i in range(len(words)):
temp_cnt = 0
if not V[i]:
for j in range(len(word)):
if word[j] != words[i][j]:
temp_cnt += 1
if temp_cnt == 1:
q.append([words[i], cnt+1])
V[i] = 1
return answer
'나의 풀이'와 같이 [변환할 수 있는 단어,cnt+1]을 queue에 append하는 방식이되 visited 리스트(V)를 만들어 미리 한번 변환했던 단어는 고려하지 않는 방식으로 더 빠른 속도를 내는 풀이였습니다.
[다른 사람의 풀이2]
from collections import deque
def solution(begin, target, words):
if target not in words :
return 0
return bfs(begin, target, words)
#최소 단계를 찾아야 하므로 bfs
def bfs(begin, target, words):
queue = deque()
queue.append([begin, 0]) #시작 단어와 단계 0으로 초기화
while queue:
now, step = queue.popleft()
if now == target:
return step
#단어를 모두 체크하면서, 해당 단어가 변경될 수 있는지 체크
for word in words:
count = 0
for i in range(len(now)): #단어의 길이만큼 반복하여
if now[i] != word[i]: #단어에 알파벳 한개씩 체크하기
count += 1
if count == 1:
queue.append([word, step+1])
위 풀이도 '나의 풀이'처럼 BFS로 구현한 방식이되, 현재 단어와 변환될 수 있는 단어를 파악할때 두글자 이상 바꿔야 변환되는 단어도 전부 고려한 후 (두글자 이상일때 break 걸지 않는 방식) 한글자만 변환하면 되는 단어만 append하는 방식이기 때문에 '나의 풀이'보다 시간이 조금 더 걸릴 수 있는 풀이였습니다.🐰🐰🐰
감사합니다.