[코테, 알고리즘] 백준 class 4 - 0-1 BFS

[13549] 숨바꼭질 3

0-1 BFS란?

BFS는 BFS인데 0-1 BFS는 무엇이냐?

가중치가 0과 1로만 주어진 그래프에서 최단경로를 찾을 때 사용할 수 있는 BFS 응용 알고리즘이다.

그래프에 가중치가 0과 1만 있을때는 다익스트라보다도 0-1 BFS가 더 효율적이다.

그냥 BFS에서는 큐(queue)를 사용하지만, 0-1 BFS에서는 덱(deque)을 사용한다.

동작과정

1. deque의 front에서 현재 노드를 꺼낸다.
2. 현재 노드에 인접한 노드(=다음 노드)들을 살핀다.
3. 만약 현재 노드까지 오는데 소비된 비용 + 다음 노드를 향하는 가중치가 다음 노드까지 가는데 소비된 비용보다 작다면, 다음 노드까지 가는데 소비된 비용을 갱신한다.
4. 이때, 다음 노드를 향하는 가중치가 0이면 다음 노드를 deque의 front에, 1이면 back에 삽입한다.
5. deque가 빌 때까지 1~4 과정을 반복한다.

파이썬에서는 deque 라이브러리를 사용해 가중치가 0이면 appendleft()로, 1이면 append()로 덱에 넣으면 된다.

코드

원래 코드

from collections import deque

N, K = map(int, input().split())
queue = deque([(N, 0)])
visited = [False] * 100001
visited[N] = True

while queue:
  now, time = queue.popleft()
  if now == K:
    print(time)
    break
  for next, second in [(now*2, time), (now-1, time+1), (now+1, time+1)]:
    if 0 <= next <= 100000 and visited[next] == False:
      queue.append((next, second))
      visited[next] = True

나는 0-1 BFS라는게 따로 있는 줄 모르고 그냥 BFS로 풀었는데 처음엔 틀렸다가 큐에 넣는 부분에서 순서를 [(now-1, time+1), (now+1, time+1), (now*2, time)] 에서 [(now*2, time), (now-1, time+1), (now+1, time+1)]으로 바꾸니까 맞았다.

고친 코드

0-1 BFS를 사용해서 풀면 다음과 같다.

from collections import deque

N, K = map(int, input().split())
dq = deque([N])
time = [-1] * 100001
time[N] = 0

while dq:
  now = dq.popleft()
  if now == K:
    print(time[now])
    break
  for next in [now-1, now+1, 2*now]:
    if 0 <= next <= 100000 and time[next] == -1:
      if next == 2*now:
        time[next] = time[now]
        dq.appendleft(next) # 이부분이 포인트
      else:
        time[next] = time[now] + 1
        dq.append(next)