[LeetCode] 212. Word Search II (C++)

문제

https://leetcode.com/problems/word-search-ii/description/

Word Search II - LeetCode

 

 

풀이

 

난이도: Hard

 

단순한 접근으로는 시간초과가 발생하는 문제이다.

 

 

DFS 접근(시간초과)

모든 word를 대상으로 board의 각 시작 지점에서 DFS를 진행한다.

board는 12x12의 크기지만 words는 최대 3만개의 10자리 단어이다.

만약 모든 board가 a로 이루어져 있고 "aaaaaaaaab"와 같은 단어를 3만개 찾게되면, 단어를 찾을 수 없기 때문에 모든 위치에서 계속 DFS가 진행된다.

DFS의 정확한 경우의 수를 계산하긴 힘들지만, board의 각 위치에서 DFS를 진행하는 경우의 수를 대략적으로 계산해보자.

 

출처: https://leetcode.com/problems/word-search-ii/solutions/878708/c-python-backtracking-with-trie-clean-concise/

 

1. 시작 위치인 1을 선택하면, 1에서 갈 수 있는 방향은 4가지 중에 하나를 선택한다.

2. 다음으로 선택된 위치에서 갈 수 있는 위치는 이전 위치를 제외한 3가지이다.

 

2는 word의 길이가 10이기 때문에 8번 만큼 반복될 수 있다.

따라서 하나의 시작 위치에서 탐색하는 경로(즉, 단어)의 경우의 수는 4 x 3^(8) 이다.

시작 위치는 12x12개이므로, 12 x 12 x 4 x 3^(8) = 3,779,136 이다.

 

3,779,136의 연산을 word의 개수인 3만번 반복하면 시간초과가 발생한다.

 

 

 

board에서 만들 수 있는 모든 단어를 Trie에 삽입

Trie에 일단 저장만 시킬 수 있다면, O(word.length)의 복잡도로 찾아낼 수 있다.

board의 각 위치에서 최대 10글자로 만들 수 있는 단어의 가짓수가 모든 탐색한다.

이는 12 x 12 x 4 x 3^(8) = 3,779,136 복잡도와 동일하다.

 

 

 

words를 Trie에 저장

 

참고한 풀이

https://leetcode.com/problems/word-search-ii/solutions/878708/c-python-backtracking-with-trie-clean-concise/

[C++/Python] Backtracking with Trie - Clean & Concise - Word Search II - LeetCode

 

 

반대로 words를 Trie에 저장 시킨다.

Trie는 저장도 O(word.length)의 복잡도이므로 최대 길이가 10인 3만개의 노드를 저장시키는데는,

300,000번의 연산이면된다.

 

최종적인 시간 복잡도는 O(12 x 12 x 4 x 3^(8) + 300,000)  = 3,779,136으로 10억번 이하라면 시간 제한안에 통과한다.

 

 

 

 

코드