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

  • flow
    가장 짧은 변환 과정을 찾는 문제.. 루트가 begin인 트리에서 자식 node들이 words에 포함되어 있고 부모로부터 변환이 가능한(철자 하나 차이) 집합을 규칙으로 하는 트리가 만들어질 때, 너비 우선 탐색을 통해서 target과 일치하는 node를 찾으면 그 때 깊이가 정답이 됨. 시간복잡도와 공간복잡도 모두 O(N) 이 되는 간단한 search 문제라고 생각됨. 카테고리가 깊이 우선탐색도 포함되어 있는데, 최단 경로 같은 것을 구할 때는 너비 우선 탐색이 깔끔한 것 같음.

  • result
    https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A6.py