너비 우선 탐색 (BFS, breadth-first search)도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
| 기능 | 특징 | 시간 복잡도 (노드 수: V, 에지 수: E) |
| 그래프 완전 탐색 | - FIFO 탐색 - Queue 자료구조 이용 |
O(V+E) |
너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다. 또한 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.
핵심 이론
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
- BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다.
- DFS와 마찬가지로 그래프를 인접 리스트로 표현한다.
- 탐색을 위해 스택이 아닌 큐를 이용한다.
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
- 큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다.
- 이때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다.
- 또한 큐에서 꺼낸 노드는 탐색 순서에 기록한다.
3. 큐 자료구조에 값이 없을 때까지 반복하기
- 큐에 노드가 없을 때까지 앞선 과정을 반복한다.
[백준 1260번] DFS와 BFS
https://www.acmicpc.net/problem/1260
[정답]
import java.io.*;
import java.util.*;
public class Main {
static boolean visited[];
static ArrayList<Integer>[] A;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 노드 개수
int m = sc.nextInt(); // 에지 개수
int v = sc.nextInt(); // 시작점
A = new ArrayList[n+1];
for (int i = 1; i <= n; i++) {
A[i] = new ArrayList<Integer>();
}
for (int i = 0; i < m; i++) {
int s = sc.nextInt();
int e = sc.nextInt();
A[s].add(e);
A[e].add(s);
}
// 번호가 작은 것을 먼저 방문하기 위해 정렬하기
for (int i = 1; i <= n; i++) {
Collections.sort(A[i]);
}
visited = new boolean[n+1]; // 방문 배열 초기화
DFS(v);
System.out.println();
visited = new boolean[n+1]; // 방문 배열 초기화
BFS(v);
System.out.println();
}
static void DFS(int node) {
System.out.print(node + " ");
visited[node] = true;
for (int a : A[node]) {
if(!visited[a]) {
DFS(a);
}
}
}
static void BFS(int node) {
Queue<Integer> queue = new LinkedList<>();
queue.add(node);
visited[node] = true;
while (!queue.isEmpty()) {
int now = queue.poll();
System.out.print(now + " ");
for (int a : A[now]) {
if(!visited[a]) {
queue.add(a);
visited[a] = true;
}
}
}
}
}
answer 배열을 n 크기로 만들어 놓고 대입한 후 출력했더니 예제 입력 3같은 경우 998번 0을 출력해 버린다. 이럴 때는 탐색 경로 배열을 만들어 값을 넣는 대신에 바로 바로 출력해야 한다.
[백준 2178번] 미로 탐색
https://www.acmicpc.net/problem/2178
문제의 요구사항은 지나야 하는 칸 수의 최솟값을 찾는 것으로, 이는 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는지를 구하는 것과 동일하다. 따라서 BFS를 사용해 최초로 도달했을 때 깊이를 출력하면 문제를 해결할 수 있다. DFS보다 BFS가 적합한 이유는 BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문이다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
// 상하좌우를 탐색하기 위한 배열 선언하기
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static boolean[][] visited;
static int[][] map;
static int n, m;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n+1][m+1];
visited = new boolean[n+1][m+1];
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
String line = st.nextToken();
for (int j = 1; j <= m; j++) {
map[i][j] = Integer.parseInt(line.substring(j-1, j));
}
}
BFS(1, 1);
System.out.println(map[n][m]);
}
static void BFS(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {x, y});
visited[x][y] = true;
while(!queue.isEmpty()) {
int[] now = queue.poll();
for (int i = 0; i < 4; i++) {
int movedX = now[0] + dx[i];
int movedY = now[1] + dy[i];
if(movedX > 0 && movedX <= n && movedY > 0 && movedY <= m) { // 좌표 유효성 검사
if(map[movedX][movedY] != 0 && !visited[movedX][movedY]) { //갈 수 있는 칸 && 방문 검사
visited[movedX][movedY] = true;
map[movedX][movedY] = map[now[0]][now[1]] + 1; // 깊이 업데이트하기
queue.offer(new int[] {movedX, movedY});
}
}
}
}
}
}
이 문제에서 핵심은 깊이를 업데이트하는 부분이다. 나는 answer 변수를 따로 두고 계속 더해가야하나 했는데 그럼 지나친 모든 경로가 다 더해지니 당연히 안된다. 맵 안의 값은 0과 1로 되어있는데, 지나갈 수 없는 곳은 0으로 둔 채 그 이전 값에 1을 더해가며 맵의 값을 계속 업데이트 해주면 원하는 목적지에 최소 경로 값이 저장되게 된다. 기억해두자.
[백준 1167번] 트리의 지름
https://www.acmicpc.net/problem/1167
풀이 과정은 다음과 같다.
1. 그래프를 인접 리스트로 저장한다. (노드, 가중치)를 표현하기 위해 노드는 클래스로 선언한다.
2. 임의의 노드에서 BFS를 수행하고 탐색할 때 각 노드의 거리를 배열에 저장한다. 예를 들어 노드 2에서 시작한다고 했을 때, 2는 4와 연결되어 있으므로 4를 방문하게 된다. 2와 4의 거리는 4이므로 distance[4]에는 4가 기록된다. 이어서 4는 2,3,5와 연결되어 있는데 2는 방문했으므로 3과 5를 방문한다. 4에서 3으로 향하는 에지 길이는 3이므로 distance[3]에 distance[4]+3을 기록한다. 그 결과 distance[3]에는 7이 기록된다. 이런 방식으로 노드를 방문하며 거리 배열을 업데이트 한다.
3. 과정 2에서 얻은 배열에서 임의의 노드와 가장 먼 노드를 찾는다. 그런 다음 그 노드부터 BFS를 다시 수행한다. 이와 마찬가지로 탐색할 때 각 노드의 거리를 배열에 저장한다.
4. 과정 3에서 배열에 저장한 값 중 가장 큰 값을 이 트리의 지름으로 출력한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Node>[] A;
static int[] distance;
static boolean[] visited;
public static class Node {
public int value;
public int distance;
public Node(int value, int distance) {
this.value = value;
this.distance = distance;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int v = Integer.parseInt(br.readLine()); // 노드 개수
A = new ArrayList[v+1];
distance = new int[v+1];
visited = new boolean[v+1];
for (int i = 1; i <= v; i++) {
A[i] = new ArrayList<Node>();
}
StringTokenizer st;
for (int i = 0; i < v; i++) { // A 인접 리스트에 그래프 데이터 저장
st = new StringTokenizer(br.readLine());
int node = Integer.parseInt(st.nextToken());
while(true) {
int E = Integer.parseInt(st.nextToken());
if(E == -1) break;
int V = Integer.parseInt(st.nextToken());
A[node].add(new Node(E, V));
}
}
BFS(1);
int max = 1;
for (int i = 2; i <= v; i++) { // distance 배열에서 가장 큰 값으로 다시 시작점 설정
if(distance[max] < distance[i]) max = i;
}
distance = new int[v+1];
visited = new boolean[v+1];
BFS(max); // 새로운 시작점으로 실행
Arrays.sort(distance);
System.out.println(distance[v]);
}
static void BFS(int index) {
Queue<Integer> queue = new LinkedList<>();
queue.add(index);
visited[index] = true;
while(!queue.isEmpty()) {
int now_node = queue.poll();
for (Node node : A[now_node]) {
if(!visited[node.value]) {
visited[node.value] = true;
distance[node.value] = distance[now_node] + node.distance; // 거리 배열 업데이트
queue.add(node.value);
}
}
}
}
}
거리 배열이 업데이트 되는 모습을 잘 보자.
[참고 자료]
- 알고리즘 코딩 테스트 자바편
알고리즘 [탐색] - 너비 우선 탐색
너비 우선 탐색(BFS : Breadth-first search)는 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.너비 우선 탐
velog.io
'알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
| 그리디 (0) | 2024.05.28 |
|---|---|
| 이진 탐색 (Binary Search) (0) | 2024.05.25 |
| 깊이 우선 탐색(DFS) (0) | 2024.05.23 |
| 기수 정렬 (Radix sort) (0) | 2024.05.21 |
| 병합 정렬 (Merge sort) (0) | 2024.05.21 |
