• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

이 문제를 경로의 문제로 보고(최단거리) 푼다면..

22.08.21 17:13 작성 조회수 177

0

안녕하세요 강사님. 질문이 있어서 남깁니다. 이 문제를 최단거리. 즉 경로 탐색 문제로 보고, DFS나 BFS를 이용해서 풀어도 문제 없을까요? 최단거리 단어를 보자마자 BFS로 풀어야 겠다 라는 생각만 했습니다.
그리고 이런 류의 문제를 dp로 풀지 DFS/BFS로 풀지 어떻게 생각해야 하는지 궁금합니다.
course-thumbnail

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

7. 알리바바와 40인의 도둑(Bottom-Up)

강의실 바로가기

답변 1

답변을 작성해보세요.

0

김태원님의 프로필

김태원

지식공유자

2022.08.28

안녕하세요^^

네. 다이나믹을 DFS나 BFS로 할 수는 있습니다. 하지만 그렇게 했을 때 시간복잡도상 타임리밋이 날 수 있을 때 다이나믹을 합니다.

이 문제는 제가 단순하게 하느라고 N을 20정도로 했는데, 실제 다이나믹이라면 1000정도로 들어올 겁니다.

이 글과 비슷한 Q&A