날짜: 2022년 1월 31일 오후 5:51
코드
Algorithm/43163.py at main · Junroot/Algorithm
풀이
- 두 단어에 글자 차이 개수 구하기
- 차이가 1인 단어들끼리 딕셔너리로 표현하기
- bfs를 이용하여 최소 변환 단계 구하기
이렇게 3가지 문제로 나뉘었다. 1, 2번은 구현 문제이므로 따로 풀이를 적지는 않는다. bfs는 너비 우선 탐색이기 때문에 출발지로부터 거리가 짧은 노드를 우선적으로 탐색한다는 것을 인지한다면 3단계를 캐치할 수 있게된다. 큐에 단어를 넣을 때 현재까지 변환한 횟수도 함께 저장하면 쉽게 최소 변환 단계를 구할 수 있다. 또한, visited 리스트를 만들어서 전부 순회했는데도 원하는 단어가 나오지 않으면 0을 리턴하면된다.
여기서 유의할 점이 begin에 해당하는 단어는 words에 속해있지 않다는 점이다. 하지만 words와 함께 딕셔너리에 추가해서 처리해도 문제가 없다. 왜냐하면, begin으로 시작했는데 다시 begin으로 돌아오는 경우는 절대 최단 경로가 되지 못하기 때문이다.