[LeetCode] 79. Word Search (C++, DFS)

문제

 

Word Search - LeetCode

Word Search - LeetCode

 

 

풀이

 

난이도: Medium 

 

Matirx로 분류되어 있지만, DFS로 해결 가능한 문제였다.

 

간단히, 문자열의 시작 문자와 동일한 위치에서부터 상하좌우 네 방향을 DFS로 탐색해 나가면 된다.

너무 간단하므로 아래에서는 follow-up 문제까지 고민해보기로 하자.

 

DFS 풀이 코드

 

 

 

 

 

 

좀 더 생각해보기 (pruning)

 

 

이번 문제의 follow-up은 다음과 같다.

 

Follow up:
 Could you use search pruning to make your solution faster with a larger board?

 

 

백준에서는 이처럼 간단한 DFS문제라고 생각하고 진행하다 보면 matrix의 크기가 이번 문제의 최대치인 6x6보다 훨씬 큰 경우가 나온다.

input이 큰 문제일수록 간단한 해결책은 시간 초과가 발생하기 쉽다.

 

follow-up은  6x6보다 더 큰 행렬이 주어질 때 가지치기(puruning)를 통한 더 빠른 탐색이 가능한지 물어보고 있다.

 

일단 가장 간단한 가지치기 방법은 다음과 같다.

 

1. 모든 칸 수보다 단어의 길이가 클 때

2. 단어에 존재하는 문자들이 실제 칸들의 문자보다 많을 때

  (예를 들어 AAAA를 찾으려 하지만 board에 A가 3개밖에 없는 경우)

 

false가 정답인 케이스는 모든 경우의 수를 탐색해 보아야 하기 때문에, 위의 두 가지 경우처럼 애초에 답이 없는 경우를 걸러내면 시간을 많이 단축시킬 수 있다. 

 

 

추가적인 방법은 다음 링크에서 소개하고 있다.

C++: How to prune the DFS to 0ms - LeetCode Discuss

 

요약하자면 b가 단 한 칸이 있고, 이외 모든 칸이 a인 경우를 생각해보자.

여기서 찾는 단어가 "aaaaa~aaab"라고 하면, 항상 a를 찾아내어 dfs 분기를 하지만 결국 최종적으로 b가 인접하지 않아 무의미한 탐색이 수도 없이 발생한다.

릿코드에는 없었지만, 다른 문제에서는 이런 예제 케이스가 존재하는 경우가 많고 결국에는 시간 초과가 발생하기 쉽다.

 

만약 단어를 "aaaaa~aaab" 대신 reverse한 "baaaa~aaaa" 로  바꾼다면 정답은 같더라도 더 빠르게 탐색할 수 있을 것이다.

이를 구현하기 위해서는 문자의 중간 위치를 기준으로 더 길게 이어지는 부분이 앞으로 가도록 단어를 reverse하는 방법이 있다.