[leetcode] 126. Word Ladder II

문제 : https://leetcode.com/problems/word-ladder-ii/

---

 

문자들 리스트인 wordList가 주어질 때, beginWord에서 한 글자씩만 바꿔서 wordList에 있는 문자열로 변환해가면서 endWord로 변환가능한 최소 변환횟수 문자열 변경 리스트들을 구하라. beginWord는 wordList에 없어도 되지만 endWord는 wordList에 있어야만 변경 가능한다. 

 

ex)

// input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

// output
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

---

bfs로 풀었다. bfs로 풀기위해 먼저 그래프 구조를 만들어야 한다.

정점은 wordList + beginWord 문자열들이다.

먼저 wordList + beginWord 문자열들을 한 문자씩 바꿔가면서 변경 가능한 문자열들을 저장한다. (간선 연결)

 

위 예시 input으로 간선 연결을 한 결과는

cog -> log, dog 
log -> cog, lot, dog 
dog -> cog, log, dot 
dot -> dog, lot, hot 
hit -> hot 
lot -> log, hot, dot 
hot -> lot, dot, hit

가 된다.

 

그래프는 만들었으니 이제 bfs를 돌려보자.

beginWord가 시작 문자열이기 때문에 beginWord,  hit 를 시작 정점으로 잡는다.

탐색하면서 변경된 문자열들을 모두 알고 있어야 하기 때문에 문자열들을 배열로 저장해둬야한다.

hit -> hot ([hit, hot])

이제 탐색한 마지막 문자열들(hot)에 대해서 다시 탐색한다.

이 때, hot 은 이미 탐색되었기 때문에 다시 탐색되면 안된다.

hot을 만약 이후에도 탐색된다고 하더라도  hot -> ... -> endWord 의 최소 길이 리스트는 항상 같을것이다.

따라서 startWord -> ... -> hot 거리가 가장 짧은 지금이 아닌 이후에 탐색하게 된다면 항상 정답이 될 수 없을 것이다. (최소 변형 횟수인 리스트를 구해야하기 때문)

따라서 이후 탐색에서 탐색되는 경우를 방지하기 위해 탐색된 노드(문자열)들을 따로 저장해둬서 이미 탐색된 문자열들은 또 탐색되지 않게 방지한다.

 

hit -> hot -> lot ([hit, hot, lot])
           -> dot  ([hit, hot, lot])

 

hit -> hot -> lot -> log ([hit, hot, lot, log])
           -> dot -> dog  ([hit, hot, dot, dog])

 

hit -> hot -> lot -> log -> cog ([hit, hot, lot, log, cog])
           -> dot -> dog -> cog ([hit, hot, dot, dog, cog])

 

bfs 탐색을 진행하면 위와 같은 문자열 변형과정들을 구할 수 있고 endWord(cog)까지 문자열이 변환되었다면 이 떄, 마지막 문자열이 cog인 문자열 리스트들이 모두 정답이 된다.

 

시간복잡도는 모든 간선의 개수이고 wordList의 개수를 N이라 했을 때, O(N^2)이 된다.

문자열들이 같은지 비교하는 연산의 경우 문자열의 길이만큼 시간이 소요되지만 제한사항에 문자의 길이의 최대값은 5이므로 이는 생략하였다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/126.%20Word%20Ladder%20II.cpp

---

알고나면 전형적인 bfs(탐색) 문제인데 적절한 알고리즘을 선택할 수 있는지, 이를 적용하기 위해 적절한 자료구조로 만들 수 있는지, 구현을 실제로 할 수 있는지에 대한 문제여서 좋은 문제같다. :+1: