이전에 dfs 알고리즘과 bfs 알고리즘에 대해 한 번 살펴본 적이 있었습니다.
시간이 오래 지나 흐릿해진 기억을 되짚어보기 위해 정리해봅니다.
BFS, DFS 두가지 모두 그래프를 탐색하는 방법입니다.
그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다.
먼저 bfs 알고리즘 부터 살펴보도록 하겠습니다.
BFS 알고리즘 (Breadth-First Search)
bfs 알고리즘은 아래와 같이 동작을 합니다.
위 예시와 같은 문제를 푼다면
1 -> 2 -> 3 -> 4
1 -> 2 -> 4 -> 3,
1 -> 3 -> 2 -> 4
1 -> 3 -> 4 -> 2
1 -> 4 -> 2 -> 3
1 -> 4 -> 3 -> 2
순서로 시작하는 모두 BFS를 이용한 경로 확인 방법입니다.
특정 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 노드로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다.
ex) 1번 노드에서 9번 노드로 이동하기 위한 최단 경로 구하기
- 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
- 너비 우선 탐색의 경우 - 1번 노드에서 가까운 노드 순서로 검색
방문할 노드들을 차례대로 저장하고, 저장한 순서대로 꺼낼 수 있는 자료 구조인 Queue를 사용한다. (FIFO: 선입 선출 방법 사용)
큐에 저장된 노드가 없을 때 까지 돌아가도록 while문을 사용하는데, 무한 루프에 바지지 않도록 주의해야한다.
최단거리 알고리즘 문제를 푸는데 특화 되어 있으며, 인접리스트, 인접 행렬을 이용하여 구현할 수 있다.
일반적으로 bfs 알고리즘을 이용하여 문제를 해결할 때는 인접리스트를 이용한다.
인접리스트를 사용할 경우에는 실제로 연결된 노드들에 대한 정보만 저장하기 때문에, 모든 벡터들의 원소의 개수의 합이 간선의 개수와 같다는 점이 있습니다. 즉, 간선의 개수에 비례하는 메모리만 차지한다고 볼 수 있지만 인접 행렬의 경우에는 노드 x 노드의 수만큼의 행렬을 무조건 메모리에 올리기 때문에 node는 많지만 edge가 적은 경우에는 매우 비효율적이기 때문입니다.
그러나 특정 노드간의 연결 유무를 확인할 때는 인접 행렬로 구현하는 것이 훨씬 빠릅니다.
요약
최단 거리 알고리즘 문제를 풀 때는 bfs가 효율적이다.일반적으로 최단거리를 구할 때는 인접 리스트 방식으로 문제를 해결하는게 좋지만특정 노드끼리의 연결 유무를 확인할 때는 인접 행렬을 사용하면 된다.
백준 bfs 문제 한개를 풀어보길 바란다.
boj.kr/16928