인프런 커뮤니티 질문&답변
작성한 질문수
답변 2
0
큰돌
지식공유자
안녕하세요 ㅎㅎ
먼저 가중치가 같은 그래프내의 최단거리 = BFS를 사용해야 합니다.
3 - K는 최단거리 문제이고 치즈는 최단거리 문제가 아니기 때문에 다른 알고리즘을 사용했습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다.
Vanellope i님께서 질문하신 3-K와 2636 치즈 문제의 알고리즘 선택에 대한 차이에 대해 설명드리겠습니다. 두 문제 모두 그래프 탐색을 필요로 하지만, 각 문제의 구조와 요구사항에 따라 최적의 탐색 방법이 달라질 수 있습니다.
BFS vs DFS 차이점
- 시간 복잡성: BFS는 동일 레벨의 노드를 먼저 탐색하기 때문에 목표 노드를 가장 처음 발견할 때까지 탐색합니다. 따라서 최단 경로를 찾는 데 유리합니다. 반면 DFS는 최상단의 루트에서 각 분기를 끝까지 탐색하고 스택을 사용하여 뒤로 돌아가는 방식으로 진행됩니다.
- 공간 복잡성: BFS는 큐를 사용하여 모든 레벨의 노드를 기억해야 하므로, DFS보다 메모리 사용량이 큰 경우가 많습니다.
문제 유형에 따른 알고리즘 선택
- 3-K (백조의 호수) 문제: 시간 효율이 필요하며, 주로 타이트한 시간 제한이 있는 그래프에서 시작점으로부터의 최단거리를 개선된 접근 방식으로 진행해야 할 때 적합한 BFS를 선택하시게 됩니다. 주로 범위를 넓혀가며 목표를 추적하는 문제입니다.
- 2636 (치즈) 문제: 전체적인 영역을 체계적으로 탐색할 때 DFS가 효율적일 수 있습니다. 물리적인 면 자체를 “녹여가면서” 처리할 수 있기 때문입니다.
이는 일반적인 권장 방식이지만, 실제 상황에서는 문제의 특성에 따라 더 적절한 방법을 사용하셔야 합니다. 알고리즘 선택의 기준은 문제의 입출력 및 조건에 따라 결정됩니다.
이전 유사한 질문 및 답변들을 통해 더 심도 있는 설명을 확인하시길 추천드립니다. 다음은 관련된 질문 URL입니다:
- 3-C 속도 차이 질문드립니다
- 이 문제 DFS 풀이는 어떤가요?
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.