[자료구조] DFS, BFS

그래프 탐색 알고리즘

그래프 : 여러개체들이 연결되어 있는 자료구조
탐색 : 특정 개체를 찾기 위한 알고리즘

대표적 문제 유형

1. 경로 탐색 유형 (최단 거리, 시간)
2. 네트워크 유형 (연결)
3. 조합 유형(모든 조합 만들기)

DFS (깊이 우선 탐색)

한 우물만 파고들며 끝을 볼 때까지 확인
재귀함수를 이용해 구현하는 것이 일반적임

# graph는 각 노드가 연결된 정보를 리스트 형태로 정리한 것
# visited 노드 방문 상태 

def DFS(graph, v, visited):
  visited[v] = True
  print(v, end=' ')

  for i in graph[v]:
    if not visited[i]:
      DFS(graph, i, visited)

BFS (너비 우선 탐색)

매 단계에서 가능한 모든 경우의 수를 확인
Queue나 LinkedList를 이용해 구현하는 것이 일반적임
현재 나의 위치에서 가장 가까운 노드를 먼저 방문하는 것으로
현재 위치는 pop해주고 방문한 곳은 체크한 뒤, 방문할 곳은 큐에 넣음

# graph는 각 노드가 연결된 정보를 리스트 형태로 정리한 것
# visited 노드 방문 상태 

def BFS(graph, start, visited):
  queue = deque(start)

  visited[start] = True
  while queue:
    v = queue.popleft() #queue.pop(0)
    print(v, end=' ')

    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

BFS와 DFS 중 어떤 것을 사용해야 할까?

BFS와 DFS 모두 그래프 탐색 알고리즘이기 때문에 어떤 방법을 사용해도 정답은 나옴
-> 자신있고 손에 익은 알고리즘을 사용하는 것이 좋음

DFS는 동작 검증이 BFS보다 쉽고, 정답과 대조하기 좋음
하지만 깊이 우선 탐색이기 때문에 수행 시간이 복불복으로 결정됨
이럴 때는 BFS를 사용해서 접근하는 것이 좋음 (시간복잡도가 낮음)

DFS, BFS 유형의 쉬운 문제들이 나왔다면 DFS로 빠르게 구현하고,
난이도가 있거나 DFS로 풀기에 시간이 오래 걸릴 것 같다면 BFS로 구현

미로 탐색과 같은 알고리즘은 최단 거리만을 가지고 탈출하는 것이므로 BFS가 적합함
하지만 미로 탐색을 하는데 가중치가 붙거나, 이동 과정에서 여러 제약이 있을 경우에는 DFS로 구현하는 것이 좋음

한 문제를 두 방식으로 풀어보고, DFS와 BFS 함수 형태를 암기해두고 바로 사용해보는 것도 좋아보임!

---

관련 백준,프로그래머스 문제

DFS, BFS 뼈대 문제

https://www.acmicpc.net/problem/1260
https://school.programmers.co.kr/learn/courses/30/lessons/43162

---

출처
https://www.youtube.com/watch?v=BsYbdUnKZ-Y