728x90
반응형
0-1 너비 우선 탐색 (0-1 Breath First Search, 0-1 BFS)
: 가중치가 0과 1만 존재하는 그래프에서 최단 경로를 찾는 알고리즘
[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) - JAVA / 자바를 사용하여 풀 수도 있는 문제이지만, 가중치가 0과 1만 존재하는 그래프라면 0-1 BFS 알고리즘이 보다 효율적으로 문제풀이가 가능하다.
특징
① 큐(Queue) 대신 덱(Deque)을 사용
② 가중치가 0과 1만 존재할 때 사용
알고리즘
1. 덱(Deque)의 front에서 이동할 다음 경로를 꺼낸다.
2. 현재 위치에서 연결된 다음 경로를 탐색한다.
3. if(출발 지점부터 현재 위치까지 누적된 가중치 + 다음 경로와 연결된 간선의 가중치 < 다음 경로까지 가는데 소비된 비용) 가중치를 갱신해준다.
4. 경로의 가중치가 갱신된 상태에서 만약 다음 경로를 향하는 간선의 가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입하도록 한다.
5. 덱에 저장된 다음 경로가 더 이상 없을 때까지 1~4 과정을 반복한다.
의사 코드 (Pseudo Code)
0-1BFS(sV, eV)
DQ ← createDeque();
enDeque(sV);
while(not isEmpty(DQ)) do {
v ← defirstDeque();
if(v == eV)
return distance[v];
for(i ← 1; i<=n; i ← i+1) do {
if(graph[v][i] == 0) {
distance[i] ← min(distance[i], distance[v] + graph[v][i]);
enfirstDeque(i);
}
else {
distance[i] ← min(distance[i], distance[v] + graph[v][i]);
enlastDeque(i);
}
}
}
return -1;
end 0-1BFS()
JAVA 코드 구현
static int bfs0_1(int sV, int eV) {
Deque<Integer> deque = new LinkedList<>();
deque.add(sV);
int distance[] = new int[n+1];
Arrays.fill(distance, Integer.MAX_VALUE); // 오버플로우가 날 수 있으므로 적당히 큰 수로 채우자
int v;
while(!deque.isEmpty()) {
v = deque.removeFirst();
if(v == e)
return distance[v];
for(int i=1; i<=n; i++) {
if(graph[v][i] == 0) {
distance[i] = Math.min(distacne[i], distance[v] + graph[v][i]);
deque.addFirst(i);
}
else {
distance[i] = Math.min(distacne[i], distance[v] + graph[v][i]);
deque.addLast(i);
}
}
}
return -1;
}
시간 복잡도 (Time Complexity) = O( V + E )
* Dijkstra Al은 O(E log E) OR O(E log V)
728x90
반응형
'알고리즘 > [JAVA_자바] 알고리즘' 카테고리의 다른 글
[알고리즘] 위상 정렬 알고리즘 (Topological Sort AL) - JAVA / 자바 (0) | 2022.03.12 |
---|---|
[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) - JAVA / 자바 (0) | 2022.03.06 |
[알고리즘] 0-1 배낭 문제 (0-1 Knapsack Problem) - JAVA / 자바 (0) | 2022.02.27 |
[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) - JAVA / 자바 (0) | 2022.02.26 |
[알고리즘] 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm) - JAVA / 자바 (0) | 2022.02.20 |