[프로그래머스] 단어 변환 ( Python 파이썬 )

programmers.co.kr/learn/courses/30/lessons/43163#

코딩테스트 연습 - 단어 변환

문제 설명

두개의 단어 begin과 target이 주어지며 단어의 집합 words가 주어집니다.

begin은 words에 있는 단어 중 하나로 변경 가능하며, 한 번에 하나의 알파벳만 변경가능합니다.

 

이러한 과정을 통해 target까지 가는데 몇 단계의 과정을 거쳐야 하는지를 출력하면 됩니다.

 

문제의 자세한 설명은 위 링크에 나와있습니다!

---

풀이 과정

문제에서 한 번에 하나의 알파벳만 변경가능하다고 했으므로,

단계별로 현재 선택한 단어와 한 글자 차이가 있는 알파벳만 모두 얻도록 하는 BFS 를 이용하면 됩니다.

 

첫 begin을 예로 들면, begin과 단 한 글자 차이만 있는 단어들을 모두 stack에 넣습니다.

이렇게 모두 stack에 넣고 나면 1단계가 완성이 됩니다.

 

2단계에서는 이 1단계에 넣은 단어들과 단 한 글자 차이만 있는 단어들을 tack에 넣게 됩니다.

그럼 이 단어들은 begin과는 2 글자 차이가 날 것이고, 현재 비교하는 것들과는 1 글자 차이가 날 것입니다.

 

이러한 식으로, 단계별로 탐색을 해나가는 bfs방식을 통해 stack에서 꺼낸 원소가 target과 일치하는지 확인하면 됩니다.

def bfs(begin, target, words, visited):
    count = 0
    stack = [(begin, 0)]
    while stack:
        cur, depth = stack.pop()
        if cur == target:
            return depth
        
        for i in range(len(words)):
            if visited[i] == True:
                continue
            cnt = 0
            for a,b in zip(cur, words[i]):
                if a!=b:
                    cnt += 1
            if cnt == 1:
                visited[i] = True
                stack.append((words[i], depth+1))
                
            

def solution(begin, target, words):
    answer = 0
    if target not in words:
        return 0

    visited = [False]*(len(words))

    answer = bfs(begin, target, words, visited)

    return answer

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !