luckyquit   4년 전

가중치가 1일때의 그래프 알고리즘 중 대표적인 DFS/BFS 문제에 요즘 빠져있습니다.

BFS문제집과 DFS문제집을 각각 풀어보고 있는데. 

DFS문제는 거의다 BFS로도 풀리는데, 


BFS문제는 몇몇은 DFS로 풀리지만, 대부분 바꾸려다가 실행시간이 훨씬 더 걸리게 되고 안 풀리는 경우가 많았습니다.

개인적으로 재귀함수를 어려워하는 편이라, 구현하기도 조금 더 까다롭다고 느낍니다.


한 때, 쉬운문제들을 풀때는 BFS문제는 DFS로 풀 수 있고 그 역도 가능하다 라는 전제를 감히 제가 세웠는데,

지금와서 보니 아닌 거 같습니다.


용도가 나눠져있으니 각각의 알고리즘으로 나눴다고 생각합니다. 

Q1. BFS는 어떤 형태일 때 최선이고, DFS는 어떤 형태일 때 최선인지? (ex- BFS는 가중치가 1인 그래프에서 최단경로를 찾는다)

Q2. 위의 본문에서 대부분의 DFS문제는 BFS로 풀린다 라는 개인적인 견해를 주장했는데, 틀렸다고 생각하신다면 이유를 알려주세요!  

답변해주시는 모든 분들 항상 감사합니다

dyk777   4년 전

우선 제 개인적인 견해임을 밝힙니다.

A1) BFS로만 되는 것으로는 질문에서 언급하셨듯이 최단거리가 있겠고, DFS만으로 되는 것은 백트래킹이 있지 싶습니다.

A2) 위의 (A1)과 직결되는 내용인데, DFS&백트래킹으로 잘 알려진 N-Queen 문제를 풀어보신다면 생각이 바뀌실 듯 합니다.

https://www.acmicpc.net/proble...

djm03178   4년 전

  1. (ex- BFS는 가중치가 1인 그래프에서 최단경로를 찾는다) - 이게 사실상 거의 유일한 경우인 것 같습니다. 물론 여기서 말하는 '최단경로'라는 것이 무엇을 의미할지는 문제에 따라서 수만 가지가 나올 수 있지만, 기본적으로 DFS가 안 되고 BFS만 써야 하는 경우는 거의 다 비슷한 문제로 환원됩니다.
  2. 어떤 상태에서의 답을 구하기 위해 어떤 경로를 따라 끝까지 들어가봐야 하는 경우에는 BFS로는 잘 안 됩니다. 마지막까지 일단 들어갔다가, 돌아오는 길에 거쳐갔던 정점들에 대한 답을 순차적으로 갱신해줘야 하는 경우가 있습니다. 그리고 BFS로 풀 수 있다고 하더라도, DFS가 훨씬 직관적이고 구현하기 편한 경우들도 무수히 존재합니다.

luckyquit   4년 전

dyk777님,   djm03178님 우선 답변 감사합니다.

두분의 답변을 보니 거의 같은 의견을 내신 거 같아서 한번에 답글을 올립니다.

아래의 제 의견 중 틀린 게 있다면 지적해주시면 감사하겠습니다.

우선 두 분의 답변을 통해 검색해본 결과, 정리된 제 생각을 말씀드리면 다음과 같습니다.

BFS 는 가중치가 1인 그래프에서 최단 경로를 찾는다. 즉, 최단 경로를 찾으면 거기서 끝.

DFS 는 가중치가 1인 그래프에서 가능한 모든 조합을 검색하는 것을 고려하는 기법이다. Backtracking과 연관지을 수 있는데, 일반적으로 재귀로 구현하여 문제의 제약조건을 만족하지 못하는 솔루션을 제거해간다.

즉, 간단하게 정리해보면 출구가 있으면 BFS, 그렇지 못한 경우는 DFS라고 정리할 수 있다고 생각합니다. 

한가지 추가 질문이 있습니다. 어제 깜빡하고 함께 질문하지 못했네요...

Q. 제가 배운 DFS의 구현 방법은 두가지 였습니다. 첫 번째는 Stack을 이욯. 두번째는 재귀적인 형태로 구현이었습니다.

저는 문제를 푼 후에도 속도 및 메모리 개선을 위해 다른 사람 코드를 보면서 개선하는 경향이 있습니다.(문제를 풀면 다른사람 코드를 볼 수 있기에)

대부분의 작성하신 코드들을 보면, 재귀의 형태로 구현을 하셨더군요. 재귀는 호출마다 생성되는 지역변수들 때문에 함수호출비용?(이 용어가 맞는지 모르겠습니다. 갑자기 헷갈리네요)이 발생하기에 재귀는 주의하며 사용해야 한다고 알고 있습니다. 물론 요즘 시대 컴퓨터는 그 정도의 메모리 사용은 큰 지장은 없겠지만... 물론 스택을 써도 메모리를 쓰긴합니다만 

재귀로 작성하신분들은 코드의 간결성 때문에 재귀를 선택하신 걸까요? 아니면 개인적인 코딩 스타일일까요? 

댓글을 작성하려면 로그인해야 합니다.