0-1 BFS

1. 개요

• 간선의 가중치가 0 또는 1인 그래프에서 최단경로를 찾아낼 수 있는 알고리즘
  • 다익스트라 알고리즘보다 시간복잡도가 적다는 장점이 있음
  • 다익스트라는 O(E * log V) 이지만, 0-1 BFS는 O(V+E)
• 일반적인 BFS 탐색과 동일하지만, 가중치가 낮은 경로부터 탐색
• 이전 정점을 통해 최단 거리가 줄어든 정점만 큐에 삽입함
• 동시에 큐는 항상 시작접으로부터 거리가 정렬된 상태

2. 예시

정점 1에서 정점 2로의 이동 = 방문 횟수 1, 가중치 1
정점 1에서 정점 3, 4를 거쳐 정점 2로의 이동 = 방문 횟수 3, 가중치 0

• 가중치가 낮은 정점을 통해 이동하는 것을 높은 우선순위로 하기 때문에, Queue대신 Deque을 이용함
• 가중치에 따라 요소를 앞쪽 또는 뒤쪽에 추가함
  • 가중치가 0인 경로를 덱의 앞에 넣어 우선 탐색하고, 가중치가 1인 경로를 덱의 뒤에 넣어 나중에 탐색할 수 있다

의사 코드

1. deque의 front에서 이동할 다음 경로를 꺼낸다
2. 현재 위치에서 연결된 다음 경로를 탐색한다
3. `출발 지점부터 현재 위치까지 누적된 가중치 + 다음 경로와 연결된 간선의 가중치`와 `다음 경로까지 가는 데 기록된 비용`을 비교한다
	3-1. 만약 기록된 비용보다 현재 노드를 들러 가는 비용이 싸다면, 가중치를 갱신한다
	3-2. 경로의 가중치가 갱신된 상태에서 만약 다음 경로를 향하는 간선의 가중치가 0이면, deque의 front에 넣는다. 1이면 back에 넣는다
4. deque에 저장된 다음 경로가 더 이상 없을때까지 1~4 반복한다

for all v in verticces:
        dist[v] = inf
    dist[start] <- 0
    deque d
    d.push_front(start)

    while d.empty() == false:
        vertex = get front element and pop as in BFS
        for all edges e of form(vertex, u):
            if travelling e relaxes distance to u:
                relax dist[u]
                if e.weight = 1:
                    d.push_back(u)
                else:
                    d.push_front(u)

시간 복잡도

• d에는 최대 O(V)개의 정점
  • while문은 O(V)번 반복함
• deque에서 pop은 O(1)
• while문 내 for문은 deque에서 추출한 정점과 인접한 정점의 개수만큼 반복
  • O(Evertext)번 반복
• if-else는 O(1)
• O(V) * { O(1) + O(Evertex) + O(1) } 이므로 O(V + E)로 정리됨

관련 문제

백준 13549. 숨바꼭질 3

백준 2423. 전구를 켜라

백준 1261. 알고스팟