[알고리즘] 0-1 너비 우선 탐색 알고리즘 (0-1 Breath First Search Algorithm, 0-1 BFS) - JAVA / 자바

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)