프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43163

[나의 풀이]

⌛ 15분

from collections import deque

def solution(begin, target, words):
    
    answer = 0
    queue = deque([[0,begin]])
    
    while queue:
        
        cnt, now = queue.popleft()
        
        if now == target:
            answer = cnt
            break
            
        for word in words:
            diff = 0
            for w1,w2 in zip(now,word):
                if w1!=w2:
                    diff += 1
            if diff == 1:
                words.remove(word)
                queue.append([cnt+1,word])
            
    return answer

시작하는 단어 begin, 타겟 단어 target, 시작에서 타겟까지 변환될 수 있는 단어 words가 주어지고 begin에서 최대 한글자씩 변환하여 words를 통해 target으로 가는 최소한의 단계를 구하는 문제입니다.🐣🐣🐣

BFS를 활용하여 queue구조에서 첫요소(시작점)를 begin으로 하고 한글자만 바꾸어 변환 가능한 words를 파악한뒤 [변환횟수,현재상태(word)]로 표현하여 append한 뒤 target까지 이를 반복하는 방식입니다.

[다른 사람의 풀이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

'나의 풀이'와 같이 queue, BFS를 활용하되 다른점으로는 '나의 풀이'에서
시간을 줄이기 위해변환 단어 리스트(words)에서 다음 변환 가능 단어들을 제외하고 remove했던 표현을 위 코드에서는 다음 변환 가능 단어 리스트(V)를 활용하여 판별했다는 점입니다.🐁🐁🐁

[다른 사람의 풀이2]

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)

유사하게 queue,BFS를 활용한 풀이입니다.🐇🐇🐇

조금 다른 점으로 현재 단어에서 한글자만 바꾸어 변환 가능한 단어들을 표현할 때get_adjacent(current,words)라는 함수 안의 yield를 통해 반복문을 순환시켰다는 점입니다.

자주 사용하지 않던 yield의 실제 활용방법을 알 수 있었습니다.