코딩테스트 복기 - 최단거리를 가장 빠르게 구할 수 있는 0-1 BFS 알고리즘

1. 문제

 

그래프 G가 V개의 정점과 E개의 간선으로 이루어지며 간선의 가중치가 0 또는 1이다.

 

이때 두 정점 사이의 최단 경로를 찾는 효율적인 코드를 작성해야한다면?

 

 

2. 다익스트라 알고리즘이 항상 정답인가?

 

많은 경우에 다익스트라 알고리즘을 선택하지만, O(E+VlogV)가 최상의 구현이지만, 최악의 경우 효과적이지 않다.

 

많은 사람들이 이 문제를 보면 다익스트라 알고리즘을 선택하고, 효율적이지 않을때, 최적화할려고 노력하지만,

 

다익스트라 알고리즘이 최상이라고 생각한다면.. 매우 간단하면서 BFS를 이용한 아주 아름다운 0-1 BFS라는 기법을 알 필요가 있다

 

보조정리(Lemma) : "BFS 수행중에 정점을 포함하는 큐는, BFS 트리의 최대 2개의 연속한 레벨의 원소만을 포함할 수 있다"

 

Lemma : "During the execution of BFS, the queue holding the vertices only contains elements from at max two successive levels of the BFS tree."

 

BFS 트리는 BFS를 실행하는 동안 만들어지는 트리이며, BFS는 인접한 정점으로만 이동하므로 큐의 모든 정점은 다른 모든 정점까지 최대 하나의 레벨만 차이난다. 

 

Explanation : The BFS tree is the tree built during the execution of BFS on any graph. This lemma is true since at every point in the execution of BFS , we only traverse to the adjacent vertices of a vertex and thus every vertex in the queue is at max one level away from all other vertices in the queue.

 

 

3. 0-1 BFS

 

이 알고리즘은 간선의 가중치가 0 또는 1인 그래프에서만 동작할 수 있어서 0-1 BFS라고 불린다.

 

간선의 가중치가 0 또는 1인 임의의 정점 u에서 BFS를 수행해보자.

 

다익스트라 알고리즘과 비슷하게, 큐에는 오직 이전 정점을 통해 최단 거리가 줄어든 정점만 큐에 넣어준다

 

u 정점에서 간선 (u,v)를 지날때, 다음 두가지 경우중 한가지가 일어난다.

 

1) u-v가 같은 레벨에 있다 (간선 u,v의 가중치가 0)

 

2) v는 u의 1레벨 위이다. (간선 u,v의 가중치가 1)

 

정점 u에 있을때, 큐에는 레벨이 L[u]인 정점이나 L[u] + 1인 정점만이 존재한다.

 

그러므로 v정점이 u에 의해 거리가 단축되었다면,

 

u와 같은 레벨이라면 큐의 앞부분에 삽입하고 

 

u보다 1레벨 높다면 큐의 뒷부분에 삽입한다.

 

그렇다면 항상 큐가 매 시점마다, 시작점으로부터 정렬된 상태를 유지할 수 있게 된다.

 

하지만 일반적인 큐는 삽입과 정렬된 상태를 유지하는데 O(1)만에 수행하지 못한다.

 

우선순위 큐도 정렬된 상태를 유지하기 위해 O(logN)을 소비하는데, 일반적인 큐는 다음의 3가지 메소드

 

1) BFS의 정점을 얻기 위해 다음 정점을 추출

 

2) 동일한 레벨일때 앞에 삽입

 

3) 다음 레벨일때 뒤에 삽입

 

하지만 Deque(double ended queue)이 이 모든 기능을 제공해준다

 

시간복잡도는 O(V+E)로 매우 효율적이다 

 

https://codeforces.com/blog/entry/22276

0-1 BFS [Tutorial] - Codeforces

 

 

https://justicehui.github.io/medium-algorithm/2018/08/30/01BFS/

[그래프] 0-1 BFS 알고리즘

 

대충 여기까지가 0-1 BFS의 원리인데... 와닿지가 않네..?

 

--------------------------------------------------

 

1) 다익스트라 알고리즘처럼 u에서 v로 이동하는 최단 거리를 구하는 알고리즘

 

2) 다익스트라 알고리즘에서 큐에서 현재 시점에서 가장 가까운 거리를 뽑기 위해, 우선순위 큐를 사용한다는 점

 

>> 우선순위 큐가 거리 기준으로 오름차순으로 정렬시켜준다는 점

 

>> 그래서 BFS에서 큐를 항상 시작점에서 거리가 정렬된 상태로 유지하기 위해

 

동일한 레벨이면 큐의 앞에 삽입하고, 다음 레벨이면 큐의 뒤에 삽입시킨다는 점

 

하긴 근데 가중치가 0,1 말고 0,1,2,3,4,.... 이렇게 여러가지면..

 

큐의 앞, 뒤에 삽입하는 행위만으로는 큐를 정렬된 상태로 유지할 수 없어서 우선순위 큐가 최선의 선택이겠네..

 

그러면 결국 가중치가 0 또는 1이 아니더라도 1 또는 3 이런식으로 2가지만 있다면 0-1 bfs가 가능하다는 소리겠는데

 

----------------------------------------------------------------------------------------------------------------------------------------

 

4. 알고리즘

 

실제 알고리즘을 정리하면 다음과 같다

 

https://nicotina04.tistory.com/168

0-1 BFS(0-1 Breadth First Search)

 

1) 모든 정점에 대해 거리 배열을 무한대로 초기화

 

2) 시작 정점에 대해 거리 값은 0으로 하고 거리가 줄어들었으므로 deque에 시작 정점을 삽입

 

3) deque의 앞에서 정점을 빼서 u라고 하자.(popleft)

 

4) 3)에서 제거한 정점 u와 인접한 정점을 v라 하고 이를 모두 검사하는데..

 

4-1) 시작점에서 u까지의 최단거리 + 1 < 시작점에서 v까지의 최단거리이면, 

 

v까지의 최단거리 = (u까지의 최단거리+1)로 갱신하고 v를 deque의 뒷부분에 삽입한다(append)

 

4-2) 시작점에서 u까지의 최단거리 < 시작점에서 v까지의 최단거리이면,

 

v까지의 최단거리 = (u까지의 최단거리)로 갱신하고 v를 deque의 앞부분에 삽입한다(appendleft)

 

5) deque에서 더 이상 꺼낼 정점이 없을때까지 3)~4)를 반복하면, 얻은 거리 배열이 시작점에서 다른 모든 정점까지의 최단거리 배열

 

5. 연습문제1

 

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

6. 풀이

 

x에서 1초 후에 x-1, x+1로 이동하는건 가중치가 1인 경우에 이동할 수 있는 경우이고,

 

x에서 0초 후에 2x로 이동하는건 가중치가 0인 경우에 이동할 수 있는 경우이다.

 

0-1BFS를 이용해서 아주 빠른 시간에 해결할 수 있다

 

그 외에 조심할 점?은 다음 정점으로 이동하는 부분이 실제 제한범위 내인지 확인해야한다는 점?

 

from collections import deque
from sys import stdin

#x에서 k로 이동하는 최단거리 구하기
def zero_one_bfs(x,k):
    
    queue = deque([x])
    
    #거리 배열을 무한으로 초기화
    dist = [10000000000000000000000000000000000000]*(100001)

    dist[x] = 0

    while queue:
        
        #왼쪽에서 정점을 빼고,
        x = queue.popleft()
        
        #도착점에 도달했다면, 그것이 최단거리고 그것을 return
        if x == k:
            
            return dist[k]
        
        #x에서 인접한 정점을 순회
        for i in [1,-1,2]:
            
            #가중치가 1인 경우에 x+1, x-1을 이동할 수 있다.
            if i == 1 or i == -1:
            
                #이동할 수 있는 좌표인지 검사하고,
                if x+i >= 0 and x+i <= 100000:
                    
                    #가중치 1을 더해서 거리가 갱신된건지 확인
                    if dist[x+i] > dist[x] + 1:
                        
                        #가중치가 1인 경우니까, deque의 뒷부분에 삽입
                        dist[x+i] = dist[x]+1
                        queue.append((x+i))
            
            #가중치가 0인 경우에 2x로 이동가능
            else:
                
                #실제 이동 가능 범위에 있는지 확인하고,
                if 2*x >= 0 and 2*x <= 100000:
                    
                    #거리 테이블이 갱신된다면...
                    if dist[2*x] > dist[x]:
                        
                        #가중치가 0인 경우에 갱신된 경우는 deque의 앞부분에 삽입
                        dist[2*x] = dist[x]
                        queue.appendleft((2*x))

                
n,k = map(int,stdin.readline().split())

print(zero_one_bfs(n,k))

 

 

 

7. 코딩테스트 복기

 

가중치가 1인 경우만 있는 그래프에서, 최단 거리를 구해야한다.

 

문제는 출발 정점이 여러개인 경우이다.

 

여러개의 출발 정점에서 동시에 출발해서, 다른 도착 정점들로 최단 시간에 도달하고자 할때, 그것을 구하는 문제

 

하지만 출발 정점은 어디서 출발해도 상관 없다

 

1번, 2번 정점이 출발 정점으로 가능하고 3번,4번으로 도착해야할때,

 

 

1번에서 3번,4번으로 이동하면 1번 > 3번으로 거리 1, 1번 > 4번으로 거리 2니까 총 거리 2만에 도달할 수 있고

 

 

 

위와 같이 하면 각각 1 거리만에 3,4를 도달하니까 거리 1이 최솟값이 된다

 

from collections import deque

INF = 1000000000000000000000

def bfs(x,graph):
    
    queue = deque([x])
    
    dist = [INF]*(n+1)
    
    dist[x] = 0
    
    while queue:
        
        x = queue.popleft()
        
        for v in graph[x]:
            
            if dist[v] > dist[x] + 1:
                
                dist[v] = dist[x] + 1
                queue.append(v)
    
    return dist

#그래프 구성
n,w = int(input())

graph = [[]*(n+1) for _ in range(n+1)]

for _ in range(w):
    
    a,b = map(int,input().split())
    
    graph[a].append(b)
    graph[b].append(a)

start = list(map(int,input().split())
target = list(map(int,input().split())

answer = INF

for s in start:
    
    dist = bfs(s,graph)
    
    max_dist = 0
    
    for k in target:
        
        if dist[t] != INF and max_dist < dist[t]:
            
            max_dist = dist[t]
    
    if max_dist != 0 and answer > max_dist:
        
        answer = max_dist

print(answer)

 

가중치가 1밖에 안되는데 다익스트라를 사용하기가 그래서, 예전에 0-1BFS를 푼 기억이 나가지고,

 

0-1BFS로 해결해볼까? 이런 생각에 과감하게 0-1 BFS를 선택

 

가중치가 1밖에 없다면, 가중치가 1인 경우만 고려하면 된다.

 

그러니까 가중치가 1인 경우 deque의 뒷 부분에 갱신된 정점을 삽입하는데.. 이것만 수행하면 된다.

 

가중치가 0인 경우는 없으니까 그거는 고려안하면 된다는 소리

 

근데 문제는 위와 같이 하면 시간초과나더라고

 

시작 정점 하나씩 순회해서 하니까...아마 시간초과겠지

 

그러다가 예전에 편의점 문제 푼게 기억이남

 

14221번: 편의점 (acmicpc.net)

14221번: 편의점

 

https://deepdata.tistory.com/797

다익스트라 응용하기 - 시작 정점은 여러개일 수도 있다

 

 

다대다 다익스트라를 하는 방법으로 처음에 다익스트라를 수행할때, 큐에 시작 정점을 모두 넣고 다익스트라를 수행했던거 기억나니?

 

그냥 이거랑 완전히 똑같은 문제였잖아?

 

그래서 시작 정점을 모두 큐에 넣고 0-1BFS를 수행한 다음에, 도착 정점까지 거리가 최대인 지점이, 

 

바로 출발 정점부터 도착 정점들을 모두 도달하는 최소거리라는 점

 

from collections import deque

INF = 1000000000000000000000

#multiple zero - one BFS
def bfs(start,graph):
    
    queue = deque()
    
    dist = [INF]*(n+1)
    
    #시작 정점을 모두 큐에 넣고 BFS 수행
    for s in start:
        
        queue.append(s)
        dist[s] = 0
    
    while queue:
        
        x = queue.popleft()
        
        for v in graph[x]:
            
            if dist[v] > dist[x] + 1:
                
                dist[v] = dist[x] + 1
                queue.append(v)
    
    #BFS가 모두 끝나면, 시작 정점들에서 각 정점까지 최단 거리가 구해짐
    return dist

#그래프 구성
n,w = int(input())

graph = [[]*(n+1) for _ in range(n+1)]

for _ in range(w):
    
    a,b = map(int,input().split())
    
    graph[a].append(b)
    graph[b].append(a)

start = list(map(int,input().split())
target = list(map(int,input().split())

answer = 0

dist = bfs(start,graph)

#도착 정점까지 거리를 조사해서, 최대거리를 찾는다.
#최대거리가, 바로 모든 도착 정점까지 도달하는데 걸리는 최솟값일것.
#시작 정점에서 동시에 출발하기 때문에
for t in target:
    
    #t까지 도달할 수 있고, 현재 최댓값 answer을 갱신할 수 있다면,
    if dist[t] != INF and answer < dist[t]:
            
        answer = dist[t]

print(answer)