인프런 커뮤니티 질문&답변
작성한 질문수
이 문제를 경로의 문제로 보고(최단거리) 푼다면..
작성
·
284
0
안녕하세요 강사님. 질문이 있어서 남깁니다. 이 문제를 최단거리. 즉 경로 탐색 문제로 보고, DFS나 BFS를 이용해서 풀어도 문제 없을까요? 최단거리 단어를 보자마자 BFS로 풀어야 겠다 라는 생각만 했습니다.
그리고 이런 류의 문제를 dp로 풀지 DFS/BFS로 풀지 어떻게 생각해야 하는지 궁금합니다.
답변 1
0
김태원
지식공유자
안녕하세요^^
네. 다이나믹을 DFS나 BFS로 할 수는 있습니다. 하지만 그렇게 했을 때 시간복잡도상 타임리밋이 날 수 있을 때 다이나믹을 합니다.
이 문제는 제가 단순하게 하느라고 N을 20정도로 했는데, 실제 다이나믹이라면 1000정도로 들어올 겁니다.