코딩 테스트에서는 다양한 알고리즘과 자료구조에 대한 이해가 중요합니다. 그 중 하나가 바로 너비 우선 탐색(BFS, Breadth-First Search)입니다. 이 글에서는 너비 우선 탐색의 기본 개념, 문제 예시, 그리고 그 문제를 해결하기 위한 단계별 접근 방법을 설명하겠습니다.
1. 너비 우선 탐색(BFS) 개요
너비 우선 탐색은 그래프나 트리 구조를 탐색하는 데 사용되는 알고리즘으로, Root 노드에서 시작하여 인접한 노드를 우선적으로 방문하는 방식입니다. 이는 주로 큐(Queue) 자료구조를 이용하여 구현됩니다. BFS는 특정 노드까지의 최단 경로를 찾는 데 유용하며, 최단 거리 문제가 있는 경우 적합합니다.
1.1 BFS의 특징
- 모든 노드를 동일한 Depth로 검색
- 최단 경로를 보장
- 메모리 사용량이 많을 수 있음
1.2 BFS의 시간 복잡도
BFS의 시간 복잡도는 O(V + E)입니다. 여기서 V는 노드의 수, E는 간선의 수를 나타냅니다. 이는 모든 노드와 간선을 각각 한 번씩 방문하기 때문입니다.
2. 문제 예시
문제 설명
주어진 그래프에서 시작 노드로부터 최단 거리를 계산하는 문제입니다. 그래프는 인접 리스트 형태로 주어지며, 시작 노드에서 도달할 수 있는 모든 노드까지의 최단 거리를 반환하는 함수를 작성하세요.
입력
- n (1 ≤ n ≤ 1000): 그래프의 노드 수
- edges: 간선 리스트의 배열, 각 간선은 [a, b] 형태
- start: 시작 노드 (1부터 n까지의 정수)
출력
start 노드에서 각 노드까지의 최단 거리를 담은 배열을 반환합니다. 도달할 수 없는 경우 -1을 사용하여 표시합니다.
2.1 예시
입력:
n = 5
edges = [[1, 2], [1, 3], [2, 4], [3, 5]]
start = 1
출력:
[0, 1, 1, 2, -1]
3. 문제 해결 과정
이 문제를 해결하기 위해서는 다음 단계로 진행합니다.
3.1 입력 데이터를 그래프 형태로 변환
우선 간선 리스트를 이용해 그래프를 인접 리스트 형태로 변환합니다. 이렇게 하면 각 노드가 인접한 노드들을 쉽게 찾을 수 있습니다.
3.2 BFS 알고리즘 구현
큐를 사용하여 시작 노드에서부터 BFS를 수행합니다. 큐에 현재 노드를 추가하고, 이를 통해 인접한 노드를 탐색합니다. 방문한 노드는 배열에 최단 거리를 기록하여 나중에 활용합니다.
3.2.1 BFS 탐색의 진행
- 시작 노드를 큐에 추가하고, 거리 배열에 초기값(0)을 설정합니다.
- 큐에서 노드를 꺼내 그 노드에 인접한 모든 노드를 확인합니다.
- 인접한 노드가 방문하지 않았다면 거리 값을 갱신하고 큐에 추가합니다.
- 모든 노드를 방문할 때까지 이 과정을 반복합니다.
3.3 최종 결과 생성
모든 노드를 탐색한 뒤, 거리 배열을 반환하여 최단 거리를 출력합니다. 도달할 수 없는 노드는 -1로 표시합니다.
4. Java 코드 예제
import java.util.*;
public class BFSDistance {
public static int[] bfsDistance(int n, int[][] edges, int start) {
List> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
// 그래프 인접 리스트 생성
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]); // 비방향 그래프
}
int[] distances = new int[n + 1];
Arrays.fill(distances, -1); // 초기 거리 -1로 설정
distances[start] = 0; // 시작 점의 거리는 0
Queue queue = new LinkedList<>();
queue.add(start);
while (!queue.isEmpty()) {
int currentNode = queue.poll();
for (int neighbor : graph.get(currentNode)) {
if (distances[neighbor] == -1) { // 방문하지 않았다면
distances[neighbor] = distances[currentNode] + 1;
queue.add(neighbor);
}
}
}
return Arrays.copyOfRange(distances, 1, distances.length); // 1부터 n까지 반환
}
public static void main(String[] args) {
int n = 5;
int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {3, 5}};
int start = 1;
int[] result = bfsDistance(n, edges, start);
System.out.println(Arrays.toString(result)); // [0, 1, 1, 2, -1]
}
}
5. 마무리
이번 강좌에서는 너비 우선 탐색(BFS)의 개념과 활용을 보여주었습니다. BFS는 최단 경로를 찾는 데 매우 효과적인 알고리즘이며, 그래프와 트리를 탐색할 수 있는 강력한 도구입니다. 여러분이 이 기법을 이해하고 코딩 테스트에서 적용할 수 있도록 연습하시기 바랍니다. 다음 강의에서는 깊이 우선 탐색(DFS)에 대해 다루겠습니다!
6. 추가 연습 문제
너비 우선 탐색을 연습하기 위한 추가 문제를 제공합니다. 아래의 문제를 풀어보세요.
문제: 최단 경로 찾기
가중치가 없는 그래프가 주어졌을 때, 시작 노드에서 모든 노드까지의 최단 경로를 구하세요. 또한 다익스트라 알고리즘을 사용하여 가중치가 있는 그래프의 최단 경로를 구하는 방법도 학습해보세요.