Leet code - 79. Word Search

leetcode.com/problems/word-search/

Word Search - LeetCode

 

인접한 셀을 탐색해서 목표하는 word가 있는지 확인하는 문제

 

Answer

접근하는 방법은 다음과 같이 생각했다.

1. 배열에서 처음 word의 character를 찾는다

2. 찾으면 4방향을 체크해서 다음 word의 characrter가 있는지 찾는다. -> 없으면 False

3. 찾은 방향으로 이동한다

4. 해당 워드가 전부 완성이 되었다면 True를 리턴한다

 

맨처음에는 Backtracking으로 접근했다가

이런 방식으로 푸는게 아니라는 생각이 계속해서 들었다

 

결국 해설을 봤고 DFS 방식을 이용해서 풀게 되었다.

 

9번라인에서 1번의 과정을 진행하고

23번의 search라인에서 코너케이스들을 점검하며

28번라인에서 search를 진행한다.

 

DFS와 Backtracking의 사용법에 대해서 헷갈리는 부분이 있어 복습이 필요해 보인다.

 

---

Reference

www.youtube.com/watch?v=m9TrOL1ETxI&t=193s

www.youtube.com/watch?v=vYYNp0Jrdv0