0-1 BFS

간단한 BFS문제인줄 알았는데, 일반적인 bfs 그래프 풀이로는

메모리초과나 시간초과가 자명한 문제였다.

 

나름대로 최적화 기준을 세워서 풀어봤지만 한참을 틀린 뒤

태그를 보고 검색을 해보니 바로 이해가 됐다.

 

왜 0-1가 붙는데?

간선의 가중치가 0과 1밖에 없어서 그렇다.

즉, 비용없이 정점을 지나는 경우와, 비용을 들여 정점을 지나는 경우로 나뉜다.

 

이게 되게 난해한 부분이, 매 순간마다

비용없이 정점을 지나는 경우를 고려해 큐에 넣어야 하기 때문에

메모리가 초과되거나, 무한루프를 돌아 시간초과가 나버린다.

 

해결 방법

덱 자료형을 사용하면 편하다.

다른 자료형을 사용해도 풀 수 있지만, 개인적으론 덱이 편했다.

 

비용을 들이지 않고 지나는 경우엔, 덱의 선두에 넣어야 한다.

비용을 들이고 지나는 경우엔 덱의 마지막에 넣어야 한다.

 

일부 문제에서는 현재의 비용이 지나갈 정점의 최소 비용보다 작은 경우에만 덱에 넣어야 하는

경우가 있으니, 문제를 잘 분석해야 한다.

 

시간 복잡도

보통 최단 거리에서 자주 사용하는 다익스트라의 시간 복잡도가

우선순위 큐를 사용하면 O((V + E) log V)

모든 정점이 출발지에서 도달 가능한 경우 O(ElogV)가 된다.

 

반면, 0-1BFS의 경우

O(V+E)의 경우로 해결 할 수 있습니다.

 

예시 문제

유명한 백준 문제를 예로 들자면

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

13549번: 숨바꼭질 3

 

점 0 ~ 100,000을 정점 V라 하고,

0, 1초에 이동을 간선 E라고 보면

 

한 정점은 2X, X + 1, X - 1의 정점으로 이동하는 3개의 간선이 있다.

여기서 먼저 방문한 정점은 항상 나중에 방문할 때 보다 최소값이다.

 

이러면 모든 정점은 한 번씩 방문하게 되고, 이 정점과 연결된 간선 역시 한 번씩 확인하게 된다.

따라서 O(V + E)가 나온다.

 

코드는 접어놨다.

import collections

n, k = map(int, input().split())
q = collections.deque()
q.append(n)
visited = [-1 for _ in range(100001)]
visited[n] = 0

while q:
    s = q.popleft()
    if s == k:
        print(visited[s])
        break
    if 0 <= s-1 < 100001 and visited[s-1] == -1:
        visited[s-1] = visited[s] + 1
        q.append(s-1)
    if 0 < s*2 < 100001 and visited[s*2] == -1:
        visited[s*2] = visited[s]
        q.appendleft(s*2)
    if 0 <= s+1 < 100001 and visited[s+1] == -1:
        visited[s+1] = visited[s] + 1
        q.append(s+1)