BFS/DFS 문제를 풀다가 접근 방식에 대해서 의문이 들어서 써보는 글.
이번 문제는 BOJ - 1937 (욕심쟁이 판다)이다.
습관적으로 문제를 BFS로 풀다보니, 자연스럽게 모든 문제를 BFS의 방식으로만 생각하고, 조금 구현이 어렵다 싶으면 DFS를 사용하곤 했었다.
이번 문제를 통해 조금 더 신중하게 문제에 접근해야겠다고 느꼈다.
발견한 문제점
판다는 항상 지금보다 더 많은 대나무가 있는 곳으로 움직이고 싶어한다.
그래서 현재 위치에서 4곳을 돌면서 더 많은 대나무가 있는 곳을 queue에 넣어주고, 움직인 횟수를 늘려가면서 답을 발견하려고 했다.
위 자체를 코드로 옮기는 것은 그렇게 어렵지 않았으나, 계속된 오답에 올라온 질문들을 살펴보니, 대부분의 사람들이 DFS + DP 로 문제를 해결하고 있었다.
괜한 오기에 계속 생각해봤는데... 알고리즘 문제 같이 푸시는 분들에게 여쭤보니, 판다의 경로가 DFS의 방식을 띄고 있다 고 하시더라.
그리고 나서 생각해보니 bfs로 하게 되면 현재의 위치에서 네 방면을 반드시 돌아보고 다음 step으로 넘어가므로, 판다의 이동방식과 맞지 않다는 것을 알게 되었다.
반례
간단하게 bfs로 풀었을 때의 반례를 보자면
BFS로 문제를 풀게 된다면 각 스텝별로 다음과 같이 방문한다 (색깔로 표시)
1 / 2,6 / 3 --> 그래서 3이라는 답이 도출된다.
근데 실제로는
1 --> 2 --> 3--> 6 이렇게 하면 4칸을 먹을 수 있게 된다.
결론 : 생각을 잘 해봅시다 😂
FE 임니다