🌱 너비 우선 탐색(BFS)
그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
| 기능 | 특징 | 시간 복잡도 (노드 수: V, 에지 수: E) |
|---|---|---|
| 그래프 완전 탐색 | FIFO 탐색 | O(V+E) |
| . | Queue 자료구조 이용 | . |
선입선출 방식으로 탐색하므로 큐를 이용해 구현한다. 또한 BFS는 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.
🌿 알고리즘
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다. 그래프는 인접 리스트로 표현한다. 또한, 큐를 이용하여 구현한다.
2. 큐에서 노드를 꺼낸 후 노드의 인접 노드를 다시 큐에 삽입하기
큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다. 이때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다. 또한 큐에서 꺼낸 노드는 탐색 순서에 기록한다.
3. 큐 자료구조에 값이 없을 때까지 반복하기
🌿 구현
import java.io.*;
import java.util.*;
public class Main {
static boolean[] visited;
static ArrayList<Integer>[] A;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
int N = readInt();
int M = readInt();
visited = new boolean[N + 1];
A = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
A[i] = new ArrayList<>();
}
while (M-- > 0) {
int s = readInt();
int e = readInt();
A[s].add(e);
A[e].add(s);
}
BFS(1);
System.out.println(sb);
}
static void BFS(int v) {
Queue<Integer> queue = new LinkedList<>();
queue.add(v);
visited[v] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
sb.append(node).append(" ");
for (int i : A[node]) {
if (!visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}
static int readInt() throws IOException {
int c, n = System.in.read() & 15;
while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
return n;
}
}
Do It 알고리즘 코딩 테스트 자바편 by 김종관
🌱 0-1 BFS(너비 우선 탐색)
가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 사용하는 그래프 알고리즘
시간 복잡도 : O(V + E) //다익스트라 : O(ElogE)
🌿 동작
Deque or 우선순위 큐 등으로 구현 가능
가중치를 곧 깊이로 해석하고 노드까지 이동 거리(가중치)가 짧은 것부터 BFS를 하게 된다.
비용이 적은 경로부터 탐색하므로 특정 간선을 2번 지나가는 경우가 없다. =>(O(E))
이 경우, 첫 방문에서 최소 거리를 찾게 된다. 모든 정점을 2번 이상 점유하는 경우도 없으므로 덱 크기는 최대 |V| 이다. (O(V))
따라서, 0-1 BFS는 O(V) + O(E) = O(V + E) 시간복잡도를 가진다.
🌿 구현 (우선순위 큐)
import java.io.IOException;
import java.util.*;
public class Main {
static boolean[] visited = new boolean[100001]; //방문 체크
//시간 오름차순, <값, 시간> 저장
static PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
static int N, K; //N : 수빈, K : 동생
public static void main(String[] args) throws IOException {
N = readInt();
K = readInt();
BFS();
}
static void BFS() {
pq.offer(new int[]{N, 0});
while (!pq.isEmpty()) {
int[] now = pq.poll();
int pos = now[0];
int time = now[1];
if (pos == K) {
System.out.println(time);
return;
}
visited[pos] = true;
//가중치가 0인 경로이므로 pos > K 라도 최소가 나올 수 있다.
if (pos * 2 <= 100000 && !visited[pos * 2]) {
pq.offer(new int[]{pos * 2, time});
}
if (pos - 1 >= 0 && !visited[pos - 1]) {
pq.offer(new int[]{pos - 1, time + 1});
}
//가중치가 1인 경로이므로 pos >= K 이면 최소가 나올 수 없다.
if (pos < K && pos + 1 <= 100000 && !visited[pos + 1]) {
pq.offer(new int[]{pos + 1, time + 1});
}
}
}
static int readInt() throws IOException {
int c, n = System.in.read() & 15;
while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
return n;
}
}
🌿 구현 (덱)
import java.io.IOException;
import java.util.*;
public class Main {
/*
* 값의 2배인 경우는 가중치가 0이므로 K를 넘더라도 이동한다.
* 따라서, time 은 최대 범위의 2배인 200,000까지 체크하도록 한다.
* */
static int[] time = new int[200001]; //시간 값 저장
static Deque<Integer> deque = new ArrayDeque<>();
static int N, K; //N : 수빈, K : 동생
public static void main(String[] args) throws IOException {
N = readInt();
K = readInt();
BFS();
}
static void BFS() {
deque.offer(N);
time[N] = 1;
while (!deque.isEmpty()) {
int now = deque.poll();
if (now == K) {
System.out.println(time[K] - 1);
return;
}
//가중치가 0인 경로이므로 pos > K 라도 최소가 나올 수 있다.
if (now * 2 <= 200000 && time[now * 2] == 0) {
time[now * 2] = time[now];
deque.offerFirst(now * 2);
}
if (now - 1 >= 0 && time[now - 1] == 0) {
time[now - 1] = time[now] + 1;
deque.offer(now - 1);
}
//가중치가 1인 경로이므로 pos >= K 이면 최소가 나올 수 없다.
if (now < K && now + 1 <= 100000 && time[now + 1] == 0) {
time[now + 1] = time[now] + 1;
deque.offer(now + 1);
}
}
}
static int readInt() throws IOException {
int c, n = System.in.read() & 15;
while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
return n;
}
}
