이 문제는 오래전에 bfs로 풀어봐서 그런지, 고민할 것도 없이 풀렸다.
하지만 이 문제를 dfs를 사용하여 풀려고 하니 어떻게 풀어야 할지를 모르겠다!.
문제가 쉬워서 그런지 마냥 재귀를 사용하여 풀 순 있겠다만,, base case도 이상하고, recursive case도 이상하다.
결국 다른 블로그를 보았고, 어떻게 푸는지는 알겠으나 완벽히 이해가 되진 않는다.
dfs로 문제를 풀거나 대충 이해하기는 어렵지 않으나, 제대로 이해하고 활용하는 것은 정말 어려운 것 같다.
특히나 백트래킹 같은 경우, 직접 그려보지 않으면 이해하기 너무 어렵다...
내가 bfs로 풀었던 정답 코드
dfs코드
뭔가 알겠으면서 모르겠다.
궁금증 1.
base case를 x,y 가 범위를 벗어나는 경우로 걸었는데, 이거보다 더 효율적인 방법이 없을까?
저렇게 되면 범위를 벗어나는 경우가 일단 호출된 후, return으로 중단해주는 방법이다. 애초에 범위가 벗어나는 경우는
제외해주는 것이 어떨까?
궁금증 2.
4개의 재귀호출 함수로 인해 상 하 좌 우를 고려해주는 코드가 된다. 근데,, 직접 그려봐야 더 와닿을 것 같다.
그려보자.
작접 그려보니, 확실히 효율적이지 않다는 것을 바로 알 수 있었다.
이미 처리된 것들을 계속 실행시키고 바로 종료하는 부분이 있다.
그래도 시간초과가 날 정도로 큰 문제는 아닌 것 같다.
아직 dfs의 용도를 정확히 모르겠다.
조합 문제를 풀 때는 dfs를 사용하니 참 편하고 시간 복잡도도 좋았다.
dfs와 관련된 문제를 더 많이 봐보자.