프로그래머스 단어 변환 문제 해설/코드 (파이썬), BFS활용문제

코드만 궁금한 분은 깃허브링크 눌러주세요!

GitHub - Rhyankwon/algorithms

 

문제 설명

 

문제 해결 논리

 

1. 주어진 단어들을 키로 하고 값은 False를 갖는 딕셔너리를 만든다.

2. 입력받은 단어들 중 시작 단어와 문자가 1개만 차이나는 단어를 모두 찾아내서

3. 아까 딕셔너리에서 지금 찾은 단어들의 값을 True로 바꾸고

4. 큐에 넣는데, 이 때 지금 찾은 단어만 넣는게 아니라 지금 몇번째 단계인지를 같이 입력한다.

5. 큐에서 단어를 새로 빼고 2~4를 반복한다. 이 때 아직 한번도 나오지 않은 단어들만 (딕셔너리에서 False표시가 된 단어들만) 

6. 큐에서 방출한 단어가 target과 같으면 현재의 단계(큐에서 같이 나왓을 것)를 리턴한다.

7. 만일 큐가 끝날 때 까지 target과 같은 값이 나오지 않으면 0을 리턴한다.

 

이 때 파이썬을 사용하는 경우 zip을 사용하면 2번을 조금 쉽게 풀 수 있다. 나는 어차피 모든 단어의 길이가 같다고 해서 for문으로 해서 단어 문자 자리 별로 비교했는데 zip을 사용하면 조금 더 ..잘해보이는 느낌으로 코딩이 가능하다.

 

간단한 큐/bfs문제이고 테스트케이스가 많지는 않아서 굳이 덱을 사용하지 않아도 푸는데 지장은 없다.