[Python] 0-1 BFS

0-1 BFS란?

가중치가 0과 1로만 이루어진 그래프 상에서 최단거리를 찾는 알고리즘
가중치가 있는 경우에는 다익스트라 알고리즘을 통해 구할 수 있음

• BFS는 큐를 사용하여 현재 노드에서 연결된 노드를 목표로 탐색하기 때문에 가중치가 있는 그래프에서는 사용 X (가중치가 있을 경우 더 멀리 연결되어 있는 노드와의 거리가 더 가까울 수 있음)
• 다익스트라 알고리즘에서는 최소힙을 사용하여 가장 가까운 거리를 가진 노드를 목표로 탐색하기 때문에 가중치가 있어도 최단거리를 찾을 수 있음

  다익스트라는 그리디, 하지만 BFS는 그리디하지 않기 때문에 가중치가 있는 그래프의 경우 BFS를 사용할 수 없음

그러나 가중치가 0 또는 1만 존재할 경우는 특수한 경우로써 BFS로 최단경로를 구할 수 있음 일반 큐 대신 양방향 큐를 사용하여 가중치가 0인 노드는 앞부분에 삽입, 1인 노드는 뒷부분에 삽입하여 가장 가까운 노드부터 BFS 탐색을 할 수 있음

BFS를 써야하는 이유

• 다익스트라 알고리즘보다 빠르기 때문에 문제에서 가중치 0,1만 보인다면 0-1 BFS로 풀 것

특징

1. 큐 대신 덱 사용
2. 가중치가 0과 1만 존재할 때 사용

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

from collections import deque

# directions: 상하좌우로 이동하기 위한 좌표
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def zero_one_bfs(grid, N):
    # 덱을 사용해 0-1 BFS 구현
    deque_queue = deque()
    # 복구 시간을 기록할 배열 (최소 경로 가중치를 저장)
    dist = [[float('inf')] * N for _ in range(N)]
    dist[0][0] = 0  # 시작 지점에서의 복구 시간은 0
    deque_queue.append((0, 0))  # 시작 지점 추가

    while deque_queue:
        x, y = deque_queue.popleft()

        # 상하좌우로 이동
        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            # 그리드 안에서만 이동
            if 0 <= nx < N and 0 <= ny < N:
                # 현재 위치에서 다음 위치로 이동할 때의 복구 시간 (0 또는 1)
                new_dist = dist[x][y] + grid[nx][ny]

                # 더 짧은 경로를 발견한 경우 갱신
                if new_dist < dist[nx][ny]:
                    dist[nx][ny] = new_dist
                    # 가중치가 0인 경우 앞에 삽입
                    if grid[nx][ny] == 0:
                        deque_queue.appendleft((nx, ny))
                    # 가중치가 1인 경우 뒤에 삽입
                    else:
                        deque_queue.append((nx, ny))

    # 도착지까지의 최소 복구 시간을 반환
    return dist[N-1][N-1]

# 예시 테스트
N = 4
grid = [
    [0, 1, 0, 0],
    [1, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 0, 1, 0]
]

# 최소 경로 출력
result = zero_one_bfs(grid, N)
print(result)

• 가중치가 0인 경로는 큐의 앞쪽에, 가중치가 1인 경로는 큐의 뒤쪽에 추가하는 방식
• 마지막 노드에 도달할 때까지 최소 복구 시간 반환