목표

• BFS를 이해한다.
• BFS의 구현을 이해한다.
• 문제를 풀어본다.

BFS

Breath-First-Search, 너비 우선탐색은 DFS와 달리 시작점에서 인접한 정점을 순서대로 모두 탐색한다.
이미 탐색했거나, 정점이 연결되지 않았을 경우를 제외하고 모두 탐색하기 때문에 완전탐색에 속한다.

왜 BFS를 사용할까?

BFS는 무방향 그래프(가중치가 없는 그래프)에서 최단 경로를 찾을 수 있는 방법이기 때문이다.

BFS의 구현

BFS의 구현에 필요한 자료구조는 배열과 큐다.

• 인접한 정점을 방문했는지 체크할 수 있는 visited 배열
• 방문할 정점의 순서를 정할 큐

BFS의 로직
1. 시작할 정점을 큐에 삽입
2. visited 배열 체크
3. while(!q.isEmpty()) 큐가 비어있지 않는 동안 정점을 탐색

• 탐색을 위해 인접한 정점을 뽑아냄 q.poll()

4. 정점에서 인접한 정점을 탐색하여 큐에 저장

• 방문한 정점의 경우 visited 배열 체크

5. 시작점과 연결된 모든 정점이 큐에 한번씩 들어가고, 방문 체크가 될 때까지 반복

탐색을 위한 그래프

그래프에서 최악의 경우는 모든 노드가 노드 간 간선을 가질 경우

• 무방향 그래프의 경우 $Vertex^2/2$ 만큼의 간선 갯수를 가짐
  6개의 정점이 있는 무방향 그래프의 경우 6 ^ 2 / 2 = 18개의 간선

• 방향 그래프의 경우 $Vertex^2$, 5개의 정점이 있는 방향 그래프의 경우 25개의 간선을 가짐

• 따라서 그래프에서 가장 중요한 건 $V$의 갯수로 $O(V)$로 표현함
  그래프에서 시간복잡도를 구성하는 요건은 다음과 같음

  1. 연결된 두 노드를 탐색하는데 걸리는 시간
  2. 한 노드에 연결된 모든 노드를 탐색하는데 걸리는 시간

인접행렬

N*M 2차원 행렬을 통해서 구현

• 구현이 간단함
• 랜덤 엑세스가 가능하기 때문에 특정 정점을 찾는 데에는 1번의 인덱스 접근
  • 연결된 두 노드를 탐색하는데 걸리는 시간 $O(1)$
• 각 노드에 연결된 노드를 모두 탐색해야 함
  • 한 노드에 연결된 모든 노드를 탐색하는데 걸리는 시간 $O(V)$

인접리스트

ArrayList를 이용하여 구현

• 랜덤 액세스 불가능, 특정 노드를 찾기 위해서 최악의 경우 정점을 전부 탐색
  • 연결된 두 노드를 탐색하는데 걸리는 시간 $O(V)$
• 하나의 노드는 List에 의해 인접한 노드에 대한 정보를 가짐
  따라서 간선 갯수가 탐색의 횟수가 됨
  • 한 노드에 연결된 모든 노드를 탐색 $O(E)$

따라서 인접행렬의 경우 $O(V^2)$
인접리스트의 경우 $O(V+E)$의 시간복잡도를 가짐

문제풀이

백준 1260

참고

벨로그