DFS BFS
그래프 요소의 문제에 접근할 때
해당 문제를 DFS, BFS 방법 중
어떤 방법을 사용하여 문제를 해결해야할지 항상 헷갈립니다.
관련해서 문제 접근 방법론에 대해 따로 강의나 정리해주시면 감사하겠습니다.
답변 2
0
안녕하세요 Data_E님.
DFS, BFS는 그래프의 완전탐색 기법이라는 공통점이 있습니다. 어떤 것을 써야할지 헷갈릴때는 대부분 DFS를 써보세요. 다만 최단거리를 구해야 하는 문제에서는 BFS를 쓰는것이 유리합니다.
BFS/DFS 큰 상관없습니다. 둘다 한번 사용해보세요. 저도 문제풀이에서 두가지 방법 다 소개해드리고 있습니다.
감사합니다 :)
0
안녕하세요, 인프런 AI 인턴이에요.
그래프 요소를 DFS와 BFS 중 어떤 방법으로 해결할지 선택하는 것은 문제의 성격과 요구사항에 따라 다르게 결정됩니다.
DFS(Depth-First Search)는 깊이를 우선으로 탐색하는 방법으로, 한 경로의 모든 노드를 탐색한 뒤 다른 경로로 이동합니다. 주로 미로찾기, 연결성 검사, 사이클 검사 등에서 사용됩니다. 스택이나 재귀 함수를 이용하여 구현할 수 있습니다.
반면, BFS(Breadth-First Search)는 너비를 우선으로 탐색하는 방법으로, 한 단계씩 진행하면서 해당 단계의 모든 노드를 탐색합니다. 주로 최단 경로 탐색, 확장 검색, 네트워크 트래픽 등에서 사용됩니다. 큐를 이용하여 구현할 수 있습니다.
따라서, 문제에 따라 어떤 방법을 사용해야할지 결정해야 합니다. 일반적으로 미로찾기와 같은 경로 문제는 DFS를, 최단 경로 탐색과 같은 최단 거리 문제는 BFS를 사용하는 경우가 많습니다. 또한, 그래프의 크기와 깊이에 따라서도 선택이 달라질 수 있습니다.
더 자세한 내용과 예제 코드는 인프런의 “김왼손의 왼손코딩” 강의 중 “[알고리즘] DFS/BFS” 강의를 참고해주세요. 강의에서는 DFS와 BFS의 개념과 구현 방법을 상세히 설명하고, 다양한 예제를 통해 실습하도록 안내합니다.
질문이 더 있으시다면 언제든지 물어보세요. 도움이 됐으면 좋겠어요.
노션 공유 링크
0
87
2
수업 중간에 내주신 문제는 해답을 알 수 없는걸까요?
0
77
2
최신 강의와 비교
0
85
2
Min Cost Climbing stairs 질문
0
76
2
노션 공유 부탁드립니다!
1
88
2
for 문에 sort 함수 를 사용하면
1
90
2
노션 공유 부탁드립니다.
0
104
2
디스코드가 올바르지 않다고 뜹니다..!
0
107
1
그래프
0
98
2
노션 공유
1
123
2
시간복잡도 질문
2
125
3
11강 질문
1
78
2
노션 공유 부탁드립니다
0
84
2
linkedList - BrowserHistory 코드 질문
0
76
1
list1.append(list2)와 list1.append(list2[:])의 차이가 무엇인가요?
1
168
1
라이브러리 사용
1
136
2
문제 교재는 따로 없는 거 맞나요?
1
202
2
LCA 관련해서 질문이 있습니다.
1
118
2
[Unique Paths] 완전탐색 / DP (후반부)
0
108
1
dp 계단오르기최소비용질문입니다.
0
109
1
Dynamic Array 의 size 정보가 저장되는 곳
2
161
2
노션공유가 안된듯 합니다
1
163
2
[코테 적용] 👉 [3번 문제] 완전탐색 (DFS, BFS) (전반부)
1
122
1
강의자료 만들 때 사용하신 프로그램이 뭘까요?
1
204
1