[프로그래머스] 파이썬 문제풀이 - 단어 변환

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=python3 

프로그래머스

 

첫 풀이

1. deque를 사용해 너비우선탐색을 사용했다

from collections import deque

def solution(begin, target, words):
    answer = 0
    visited=[0 for _ in range(len(words))]
    q=deque()
    q.append(begin)
    while q:
        word=q.popleft()
        if word==target:
            answer=visited[words.index(target)]
            break
        for i in range(len(words)):
            if visited[i]==0:
                check=0
                for j in range(len(word)):
                    if words[i][j]!=word[j]:
                        check+=1
                if check==1:
                    if word==begin:
                        visited[i]=1
                    else:
                        visited[i]=visited[words.index(word)]+1
                    q.append(words[i])
    return answer

 

더 나은 답안

1. target이 words 리스트 안에 없으면 탐색을 진행할 필요가 없어서 위에서 컷하는 코드를 추가했다

from collections import deque

def solution(begin, target, words):
    answer = 0
    if target not in words:
        return answer
    visited=[0 for _ in range(len(words))]
    q=deque()
    q.append(begin)
    while q:
        word=q.popleft()
        if word==target:
            answer=visited[words.index(target)]
            break
        for i in range(len(words)):
            if visited[i]==0:
                check=0
                for j in range(len(word)):
                    if words[i][j]!=word[j]:
                        check+=1
                if check==1:
                    if word==begin:
                        visited[i]=1
                    else:
                        visited[i]=visited[words.index(word)]+1
                    q.append(words[i])
    return answer

 

배운 점

1. 탐색 알고리즘을 배우고 있었는데 적용해볼 수 있었다

2. 탐색 문제에서는 전체를 탐색하는 만큼 조건에 따라 위에서 컷하면 시간을 단축할 수 있다