bfs 문제 dfs 로 풀 수 있나요?

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-B

작성

안녕하세요. 그래프 문제만 나오면 dfs로 풀려고 합니다.ㅜㅜ 둘 중에 어떤 것으로 풀어야 하는 지 구분하는 방법이 있나요? 그리고 2589문제에서 <dfs로 짜고 기저 사례로 부터 1을 반환 시켜서 더해 나가는 방식> 또는 <dfs에 거리 파라미터를 추가하고 함수 호출할 때마다 1씩 증가시켜서 기저 사례에서 vector에 넣는 방식> 으로 풀어도 될까요?

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

둘 중에 어떤 것으로 풀어야

음 이렇게 생각하시면 됩니다.

가중치가 같은 그래프내에서 최단거리 또는 시간을 찾는다 = 무조건 BFS로 해야 합니다.

그외 어떤 그래프내에서 탐색을 할 때는 둘 다 괜찮습니다.

2589문제에서 <dfs로 짜고 기저

이 문제는 최단거리를 구하는문제이기 때문에 BFS로 풀어야 합니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

hayoung10.lim님이 질문하신 내용에 대한 답변을 찾기 위해 몇 가지 유사한 질문과 답변을 찾아보았습니다.

3 - D : 4179 질문있습니다
- 질문 요약: BFS와 DFS의 차이를 이해하고 특정 상황에서 어떤 알고리즘을 사용해야하는지에 대한 질문입니다.
- 답변 요약: BFS는 주로 최단 거리를 찾는 문제에서 사용되며, DFS는 모든 경로를 탐색하는 데 적합합니다. 각 문제의 요구사항에 따라 선택해야 합니다.
2-A BFS 질문 있습니다.
- 질문 요약: BFS 코드 검토를 요청하며, 최단 거리 구하는 BFS의 기본적인 사용법에 대해서 질문합니다.
- 답변 요약: BFS는 최단거리를 BFS 함수 내부에서 갱신하며 푸는 것이 좋고, 단순히 이동 횟수를 증가시키는 접근은 바람직하지 않다는 내용입니다.
그래프 문제 해결 방식 관련
- 질문 요약: 그래프 문제 해결 시 BFS와 DFS 중 선택하는 기준에 대한 질문입니다.
- 답변 요약: 문제의 요건에 따라 선택하는 것이 중요하며, 각 기법을 언제 사용해야 하는지 설명합니다.

hayoung10.lim님의 질문에서도 기본적으로 동일한 원칙이 적용됩니다. DFS와 BFS의 선택은 문제의 특성에 따라 달라지며, 최단 거리와 같은 문제에서는 BFS가 적합합니다. DFS를 사용한 접근도 가능하지만, 문제 요구사항을 충족하기 위해서는 더 많은 주의가 필요합니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

bfs 문제 dfs 로 풀 수 있나요?