3월 30일(목) 욕심쟁이 판다(DFS+DP)

[Taehyeon-Kim]

욕심쟁이 판다(DFS+DP)

처음 들었던 생각

문제 풀면서 생각 흐름, 아이디어, 유형, 접근 방식 등을 잘 정리해놓는게 정말 중요하다는 생각이 다시 한 번 든다.
사실 아직 재귀가 어렵다. .. 복습 필요

1. 일단 상하좌우 이동이 나오면 구현, bfs+dfs, 시뮬레이션 느낌이 항상 강하게 든다.
2. 판다의 이동을 보니 그래프 탐색이 들어가야 한다는 생각이 들었다. (모두가 당연히 그런 생각을 하겠지?)
3. 그 후에는 어떻게 하면 최대로 많이 살아남으면서 이동을 할 수 있을까를 생각해보면서 그리디하게 경우를 손으로 나열해보았다.

• 1-7-5 (3칸), 2-5-11-15(4칸), 3-6-7-15(4칸) ...
• 충분히 작은 칸부터 이동을 시작해야 최대한 많이 살아남지 않을까라는 그리디한 생각을 해보았다.
• 특별한 규칙이 없어서 모든 경우를 다 탐색해봐야겠다라는 결론이 생겼다.

4. 그래서 dfs로 모든 칸을 다 탐색해보기로 했다.
5. 처음에 시간 복잡도를 잘못 계산해서 dfs니까 (V+E), 모든 칸 탐색이니까 (V^2) 따라서 V^3 정도의 시간복잡도가 나오겠구나. 그럼 연산 횟수가 대략 1억 2500만 정도가 된다. 그럼 문제에서 제시한 2초안에 모든 탐색이 가능하지 않나라는 생각이 들었다.
6. 그런데 어림도 없었다. 30%지나면서 시간 초과 발생...
7. 이미 탐색한 공간을 다시 탐색하지 않으려면 메모이제이션이 필요했다. 여기서 dp가 쓰이는 것이었다. 상하좌우에서 들어오는 쪽에서 이미 값이 저장되어 있다면, dfs(상하좌우칸) + 1과 dfs(현재칸)에서 최대를 최종적으로 저장해놓고 사용하면 되는 것이었다.