우선 제 개인적인 견해임을 밝힙니다.
A1) BFS로만 되는 것으로는 질문에서 언급하셨듯이 최단거리가 있겠고, DFS만으로 되는 것은 백트래킹이 있지 싶습니다.
A2) 위의 (A1)과 직결되는 내용인데, DFS&백트래킹으로 잘 알려진 N-Queen 문제를 풀어보신다면 생각이 바뀌실 듯 합니다.
우선 제 개인적인 견해임을 밝힙니다.
A1) BFS로만 되는 것으로는 질문에서 언급하셨듯이 최단거리가 있겠고, DFS만으로 되는 것은 백트래킹이 있지 싶습니다.
A2) 위의 (A1)과 직결되는 내용인데, DFS&백트래킹으로 잘 알려진 N-Queen 문제를 풀어보신다면 생각이 바뀌실 듯 합니다.
두분의 답변을 보니 거의 같은 의견을 내신 거 같아서 한번에 답글을 올립니다.
아래의 제 의견 중 틀린 게 있다면 지적해주시면 감사하겠습니다.
우선 두 분의 답변을 통해 검색해본 결과, 정리된 제 생각을 말씀드리면 다음과 같습니다.
BFS 는 가중치가 1인 그래프에서 최단 경로를 찾는다. 즉, 최단 경로를 찾으면 거기서 끝.
DFS 는 가중치가 1인 그래프에서 가능한 모든 조합을 검색하는 것을 고려하는 기법이다. Backtracking과 연관지을 수 있는데, 일반적으로 재귀로 구현하여 문제의 제약조건을 만족하지 못하는 솔루션을 제거해간다.
즉, 간단하게 정리해보면 출구가 있으면 BFS, 그렇지 못한 경우는 DFS라고 정리할 수 있다고 생각합니다.
한가지 추가 질문이 있습니다. 어제 깜빡하고 함께 질문하지 못했네요...
Q. 제가 배운 DFS의 구현 방법은 두가지 였습니다. 첫 번째는 Stack을 이욯. 두번째는 재귀적인 형태로 구현이었습니다.
저는 문제를 푼 후에도 속도 및 메모리 개선을 위해 다른 사람 코드를 보면서 개선하는 경향이 있습니다.(문제를 풀면 다른사람 코드를 볼 수 있기에)
대부분의 작성하신 코드들을 보면, 재귀의 형태로 구현을 하셨더군요. 재귀는 호출마다 생성되는 지역변수들 때문에 함수호출비용?(이 용어가 맞는지 모르겠습니다. 갑자기 헷갈리네요)이 발생하기에 재귀는 주의하며 사용해야 한다고 알고 있습니다. 물론 요즘 시대 컴퓨터는 그 정도의 메모리 사용은 큰 지장은 없겠지만... 물론 스택을 써도 메모리를 쓰긴합니다만
재귀로 작성하신분들은 코드의 간결성 때문에 재귀를 선택하신 걸까요? 아니면 개인적인 코딩 스타일일까요?
댓글을 작성하려면 로그인해야 합니다.
luckyquit 4년 전
가중치가 1일때의 그래프 알고리즘 중 대표적인 DFS/BFS 문제에 요즘 빠져있습니다.
BFS문제집과 DFS문제집을 각각 풀어보고 있는데.
DFS문제는 거의다 BFS로도 풀리는데,
BFS문제는 몇몇은 DFS로 풀리지만, 대부분 바꾸려다가 실행시간이 훨씬 더 걸리게 되고 안 풀리는 경우가 많았습니다.
개인적으로 재귀함수를 어려워하는 편이라, 구현하기도 조금 더 까다롭다고 느낍니다.
한 때, 쉬운문제들을 풀때는 BFS문제는 DFS로 풀 수 있고 그 역도 가능하다 라는 전제를 감히 제가 세웠는데,
지금와서 보니 아닌 거 같습니다.
용도가 나눠져있으니 각각의 알고리즘으로 나눴다고 생각합니다.
Q1. BFS는 어떤 형태일 때 최선이고, DFS는 어떤 형태일 때 최선인지? (ex- BFS는 가중치가 1인 그래프에서 최단경로를 찾는다)
Q2. 위의 본문에서 대부분의 DFS문제는 BFS로 풀린다 라는 개인적인 견해를 주장했는데, 틀렸다고 생각하신다면 이유를 알려주세요!
답변해주시는 모든 분들 항상 감사합니다