프로그래머스 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하는 방식이기 때문에 '나의 풀이'보다 시간이 조금 더 걸릴 수 있는 풀이였습니다.🐰🐰🐰

감사합니다.