[Algorithm] 0-1 BFS

0-1 BFS란?

BFS를 기반으로 가중치가 0,1로 주어진 그래프에서 최단경로를 찾아낼 수 있는 알고리즘이다.

기본적으로 그래프에 대한 이해와 최단경로 다익스트라 알고리즘에 대한 이해가 필요하다.

최단경로 알고리즘에는 다익스트라 알고리즘을 사용할 수 있지만, 시간복잡도가 O(ElogE) 또는 (ElogV)인 반면에 0-1 BFS는 O(V+E)의 시간 복잡도로 문제를 해결할 수 있다.

 

가중치 0인 정점이 존재하기 때문에, 실제로 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야한다.

그렇기 때문에 결과 값이 방문 횟수의 최소가 아닌 가중치의 최소인 경우를 찾기 위해서는 가중치가 낮은 경로부터 탐색해야한다.

 

가중치가 낮은 정점으로의 이동을 높은 우선 순위로 해야하기 때문에, 덱의 가장 앞단(front)에 삽입해야한다.

BFS와 동일하게 간선의 갯수(E)만큼 탐색을 하게되고, 정점의 갯수(V)만큼 중복없이 방문하기 때문에 시간 복잡도는 O(V+E)로 동일하다.

 

특징

  ① 큐(Queue) 대신 덱(Deque)을 사용

  ② 가중치가 0과 1만 존재할 때 사용

 

코드(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;
}

 

정리

1. 덱(Deque)의 front에서 이동할 다음 경로를 꺼낸다.
2. 현재 위치에서 연결된 다음 경로를 탐색한다. 
3. if(출발 지점부터 현재 위치까지 누적된 가중치 + 다음 경로와 연결된 간선의 가중치 < 다음 경로까지 가는데 소비된 비용) 가중치를 갱신해준다.
4. 경로의 가중치가 갱신된 상태에서 만약 다음 경로를 향하는 간선의 가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입하도록 한다.
5. 덱에 저장된 다음 경로가 더 이상 없을 때까지 1~4 과정을 반복한다.