[프로그래머스 level3 단어 변환] dfs/bfs 활용하기 !

해결해야하는 문제는 다음과 같았다.

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

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

 

begin 단어를 변환하여 target이 되도록 하는데 최소 경우의 수를 구해야한다고 하였기 때문에 모든 경우의 수를 수행하며 최소 경우의 수를 탐색할 수 있는 길찾기 방법인 dfs/ bfs를 활용해야 겠다고 생각하였다.

 

1. 한번에 한 개의 알파벳을 변환할 수 있다고 하였기 때문에 현재 단어를 변환하기 위해 words에서 현재 단어와 한 개의 다른 단어가 있는 것이 무엇인지 찾아야 한다.

def difference_num을 정의하여 몇개의 알파벳이 현재 단어와 임시 단어가 다른지 반환해주는 함수를 정의하였다.

 

2. target이 words에 없는 경우 변환할 수 없으므로 0을 리턴해준다.

 

3. answer은 무한대로 정의하고, 변환횟수는 0으로 정의하였다. 그리고 stack의 역할을 수행하는 리스트를 선언하고 방문했는지 여부를 작성하기 위한 visited 배열을 false로 초기화하였다.

 

4. stack에 첫번째 원소인 begin을 넣는다.

 

5. dfs/bfs 수행

stack이 빌때까지 작업을 수행한다.

word는 stack에 있는 단어이다.

word가 target과 일치하는 경우, answer가 현재 단어까지 변환횟수(count)보다 작으면 answer를 업데이트해주고 count를 0으로 한다.

일치하지 않는 경우, words에서 현재 단어와 다른 곳이 한군데이고 방문하지 않았던 단어가 있다면, 방문 표시를 해주고 stack에 현재 단어를 추가해준다.

그리고 한 턴이 돌았을 때 count + 1을 해준다.

 

이러한 아이디어를 바탕으로 작성한 코드는 다음과 같다.

def difference_num(a1, a2) :
    differ = 0
    for i in range(len(a1)) :
        if a1[i] != a2[i] :
            differ += 1
            
    return differ
    
def solution(begin, target, words):
    if target not in words :
        return 0
    
    answer = int(1e9)
    count = 0
    stack = []
    visited = [False] * len(words)
    stack.append(begin)
    while stack :
        word = stack.pop()
        if word == target :
            if count < answer :
                answer = count
                count = 0
        else :
            for i in range(len(words)) :
                if difference_num(words[i],word) == 1 and not visited[i]:
                    stack.append(words[i])
                    visited[i]=True
        count += 1
        

    
    return answer