[알고리즘][탐색] 너비탐색(BFS) & 깊이탐색(DFS)

많은 탐색 / 길찾기 알고리즘의 기본이 되는 너비탐색과 깊이탐색입니다. 

 

특히 너비탐색의 경우에는 최단경로 길찾기의 기본적인 탐색 알고리즘입니다. 앞으로 진행할 길찾기 알고리즘 포스팅을 위해 먼저 정리할 목적으로 포스팅을 합니다.

너비탐색과 깊이탐색은 탐색 방법이고, 이를 통해 다양한 길찾기 알고리즘이 파생됩니다. (다익스트라, A* 등)

 

포스팅 순서는 아래와 같습니다.

1. 너비탐색
   • 개요
   • 장단점
   • 구현방법
   • 사용예시
2. 깊이탐색
   • 개요
   • 장단점
   • 구현방법
   • 사용예시

 

 

1. 너비탐색 (BFS)

• 개요
  • 시작 정점으로부터 인접한 거리순으로 주변으로 넓게 퍼지는 탐색
    • 종이에 먹물이 퍼지는 것과 같음.
• 장단점
  • 장점
    • 로직이 단순하다.
    • 최초 발견 루트를 최단경로라고 보장할 수 있다.
    • 언제나 같은 거리 결과값을 얻을 수 있다.
  • 단점
    • 비교적 많은 저장공간이 필요하다.
• 구현방법
  • 큐를 활용하여 구현 ( 선입선출 )
    • 1. 시작 노드를 현재 노드로 설정.
    • 2. 현재 노드를 탐색된 노드로 저장.
    • 3. 현재 노드의 주변 노드 중 탐색되지 않은 노드를 탐색
    • 4. 3번의 노드를 큐에 저장. / 탐색된 노드로 저장.
    • 5. 현재 노드의 주변 노드가 모두 탐색된 노드가 될 때까지 3~4 반복
    • 6. 큐에서 다음 노드를 꺼내 현재 노드로 설정. 
    • 7. 목표에 도착할 때까지 5~6 반복. (전체탐색의 경우, 큐가 빌 때까지 진행.)
• 예시
  • 최단경로 판별에 유용
  • 길찾기의 기본으로 유용

 

2. 깊이탐색 (DFS)

• 개요
• 시작 정점으로부터 각 분기 / 방향 별로 깊게(완전하게) 탐색하고 다음 분기 / 방향으로 넘어가는 탐색
  • 미로찾기와 같음.
• 장단점
• 장점
  • 로직이 단순하다.
  • 비교적 적은 저장공간
• 단점
  • 최초로 구해지는 길이 최단이라는 보장을 할 수 없다.
    • 최단경로 길찾기에 적합하지 않음.
  • 적절한 제한을 두지 않는다면 한쪽 분기에 과도하게 깊이 빠질 수 있음.
    • 재귀함수의 경우 stack overflow 우려 (깊이 제한 필요)
  • 탐색하는 방향 우선순위에 따라 결과가 다르게 나올 수 있다.
• 구현방법
• 스택 또는 재귀함수로 구현 (후입선출) 
  • 1. 시작 노드를 현재 노드로 설정.
  • 2. 현재 노드를 탐색된 노드로 저장.
  • 3. 현재 노드의 주변 노드 중 탐색되지 않은 노드 탐색 
  • 4. 3번의 노드를 스택에 저장 / 탐색된 노드로 저장.
  • 5. 현재 노드의 주변노드가 모두 탐색될 때까지 3~4 반복
  • 6. 스택에서 다음 노드 (최근에 들어간) 를 꺼내 현재 노드로 설정.
  • 7. 목표에 도착 또는 전체 순회를 할 때까지 5~6 반복. (전체 탐색의 경우 스택이 빌 때까지 진행)

• 예시
  • 자동 미로 생성기

 

 

 

 

 

여담

• 너비탐색과 깊이탐색의 구현방법의 차이는 사실상 큐와 스택입니다. 그 외 돌아가는 기본 로직은 비슷합니다. 
• 앞으로 4~5 포스팅 동안 길찾기 알고리즘을 시리즈로 할 생각입니다. 최종적으로는 D* lite 알고리즘까지 가는 것이 목표이며, 이를 위해 하나씩 과정을 밟아갈 예정입니다.
  • 하여 이후 길찾기 알고리즘의 순서는 A*, LPA*, D* lite 알고리즘 순으로 포스팅 할 예정입니다.

 

* 포스팅내에 잘못된 내용이나, 문의사항 있으시면 언제든 댓글로 지적해주시면 감사하겠습니다.