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

(주)그렙

 

[programmers] 프로그래머스 Level3 단어 변환

(파이썬 Python)

 

* 문제출처 : 프로그래머스 코딩 테스트 연습, 알고리즘 문제

 

 

* bfs를 이용한 문제이다.

 

우선 문제를 보고 왜 bfs를 떠올리게 되었는지 천천히 생각해보아야 한다. bfs/dfs의 문제의 유형이기 때문에 bfs 아니면 dfs가 아니라, 문제의 어느 부분을 통해 bfs/dfs를 떠올리게 되었는지 생각해나가며 풀어나가야 한다.

 

 

 

 

 

1) 문제

---

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

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

 

 

 

 

 

2) 코드

---

 

def check_diff(start, end, length) :
    cnt_diff = 0
    
    for i in range(0, length) :
        if (start[i] != end[i]) :
            cnt_diff += 1
            
    return cnt_diff
 
def solution(begin, target, words):
    INF = 9999
    words_len = [INF] * len(words)
    
    answer = INF
    
    queue = []
    queue.append([begin, 0]) 
    
    word_len = len(begin)
    
    while (len(queue) != 0):
        popped = queue.pop(0)
        popped_word = popped[0]
        popped_length = popped[1]
        
        if (check_diff(popped_word, target, word_len) == 0):
            if (popped_length < answer):
                answer = popped_length
        
        for i in range(0, len(words)):
            if (check_diff(words[i], popped_word, word_len) == 1):
                if (popped_length < words_len[i]):
                    words_len[i] = popped_length
                    queue.append([words[i], popped_length + 1])
    
    if (answer == INF) :
        answer = 0
    
    return answer

 

 

 

 

 

 

 

3) 풀이 과정

---

(향후 작성 예정)

 

 

 

 

 

 

< < 사고 과정 > >

---

1. 문제를 읽고, bfs를 이용해야 겠다는 생각

 

2. 최적화 기법으로 이미 순회한 길에 대해서는 다시 접근하지 않기 위해 INF를 설정

 

3. deque보다는 그냥 queue를 만들어서 해결

 

 

 

 

 

4) 정리 노트

---

X