고급 BFS, DFS 는 어떻게 공부해야 할까요?

Question

안녕하세요! 하반기 채용 때문에 코딩테스트 찾아보다가 제가 너무 원했던 강의라서 결제 후에 개념 위주로 빠르게 보는 중입니다. 요약하자면 코딩테스트에서 DFS나 BFS 문제들이 나올 시에 기본적인 내용 + 문제해결력(테크닉) 으로 나오는 것 같은데 테크닉 적인 부분은 어떻게 공부를 해야될까요? 가령 https://school.programmers.co.kr/learn/courses/30/lessons/1832   풀이를 찾아보면 3차원(checked)으로 풀면 풀리긴 하는데, 제 직관으로는 각 그래프 경로를 분리해낸다는 컨셉이 당연하게 느껴지지가 않더라구요. 이런 까다로운 문제를 상대하려면 어떤 부분이 잘 준비되어 있어야 할까요? 강의 중에 비슷한 문제가 있다면 그부분 해설강의 꼼꼼히 봐보려고 합니다

알리 Ally · Answer

안녕하세요. lee님! 해당 문제는 그래프로 해석해서 푸는 것보단, DP로 해석해서 푸는 것이 더 적합하다고 할 수 있습니다.   [DP로 해석해서 푸는 게 더 타당한 이유] '섹션4의. 실전 문제풀이1' DP 문제인 'BOJ 11726' 강의에서 ‘경우의 수를 구하는 문제이고 경우의 수를 어떤 수로 나눈 나머지를 구하는 형식의 문제라면 DP문제일 확률이 높다’고 언급하였으니 해당 강의를 참고해보시면 좋을 거 같습니다.   [DP 관련 문제를 잘 푸는 법] DP 문제를 잘 풀려면 문제의 재귀적인 구조를 찾아 DP Table을 적절히 만들 수 있어야 하는데요. 예를 들어, 올려주신 문제에서는 DP Table을 dp[i][j] 를 (i, j)까지 도달하는 경우의 수 로 정의해보면 문제를 쉽게 접근할 수 있습니다. 정확하게는 보행할 수 없는 경우도 고려해야 하므로 dp[i][j] 를 위에서 왔는지 왼쪽에서 왔는지를 고려해주어야 합니다. 따라서 dp[i][j] = {(i- 1, j)에서 (i, j)를 왔을 때의 경우의 수, (i, j - 1)에서 (i, j)를 왔을 때의 경우의 수} 와 같이 dp[i][j] 는 2가지 정보를 담게끔 DP Table을 설계해줘야 합니다.   위와 같이 DP Table을 잘 설계하면 쉽게 풀 수 있는 문제입니다. 위 답변이 잘 이해가 안 가신다면, DP 관련 강의인 '섹션3. 필수 알고리즘1'의 DP와 관련된 강의들을 최대한 이해하며 들으시는 것을 추천드립니다. 더불어 여유가 되신다면 '섹션3. 필수 알고리즘1'의 브루트포스 알고리즘 관련 내용도 들으시면 문제를 접근할 때 도움이 많이 될 거 같습니다.   [추가적으로] 추가적으로 문제를 접근할 때 그래프 문제가 아닌 문제를 그래프 문제로 해석하여 접근하는 경우가 빈번하다면 '섹션6. 그래프 알고리즘' 파트를 보시면 그래프는 어떤 문제에 쓰이는지 더 잘 이해하실 수 있을겁니다. 혹여나 DP 파트를 수강한 후에도 올려주신 문제나 DP 문제에 대해 이해가 안 가신다면, 추가 질문 남겨주세요.   또 궁금하신 점 있으시면 언제든 질문 부탁드립니다. 감사합니다. :)