Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 그래프의 두 정점 사이 최소 페널티 경로 찾기 (비트 OR 응용)

문제 개요

무방향 가중치 그래프가 주어졌을 때, 시작 노드 a에서 도착 노드 b까지 이동하는 경로 중 페널티(penalty)가 가장 작은 경로를 찾는 문제입니다. 여기서 경로의 페널티란 경로에 포함된 모든 간선 가중치를 비트 OR(bitwise OR) 연산한 값을 의미합니다. 즉, 우리는 이러한 '최소 페널티' 경로를 찾아야 하며, 두 노드 사이에 경로가 존재하지 않는 경우에는 -1을 반환해야 합니다.

예시

예를 들어 입력이 아래와 같다고 가정해 봅시다.

파이썬으로 그래프의 두 정점 사이 최소 페널티 경로 찾기 (비트 OR 응용)

시작 정점(s) = 1, 끝 정점(e) = 3일 때 출력은 15가 됩니다.

정점 1과 3 사이에는 두 개의 경로가 존재합니다. 최적 경로는 1→2→3이며, 이때 경로의 비용은 (10 OR 5) = 15입니다.

접근 방법

이 문제는 다익스트라(Dijkstra) 알고리즘을 응용하여 해결할 수 있습니다. 비트 OR 연산은 간선을 추가할수록 누적값이 절대 줄어들지 않는(단조 증가하는) 특성이 있으므로, 최소 힙(priority queue)을 활용한 탐색과 잘 어울립니다.

다만 일반 최단 경로 문제와 다른 점이 하나 있습니다. 같은 정점에 도달하더라도 누적된 OR 값이 서로 다른 여러 상태가 존재할 수 있습니다. 예를 들어 누적값 1(이진법 01)과 2(이진법 10)는 단순한 크기 비교만으로는 우열을 가릴 수 없으며, 이후 간선과 OR 연산을 수행할 때 어느 쪽이 유리해지는지 달라질 수 있습니다. 따라서 방문 처리를 할 때 정점만이 아니라 (누적 비용, 정점) 쌍 전체를 기준으로 삼아야 합니다.

해결 단계

  • helper() 함수 정의: 그래프 G, 시작 정점 s, 끝 정점 e를 매개변수로 받습니다.
    • v := 방문한 (비용, 정점) 상태를 저장하는 새로운 집합
    • c := 크기 n의 리스트, 모든 값을 무한대(inf)로 초기화
    • heap := (0, s) 쌍을 담은 새로운 최소 힙
    • 힙이 빌 때까지 다음을 반복합니다.
      • cst, cur := 힙에서 가장 작은 항목을 꺼냄
      • c[cur] := min(cst, c[cur])
      • (cst, cur)가 이미 v에 존재한다면 다음 반복으로 건너뜀
      • cur이 e와 같다면 c[cur]을 반환
      • (cst, cur)을 v에 추가
      • G[cur]의 각 이웃(neighbor)과 간선 비용(n_cost)에 대해 (n_cost OR cst, neighbor)를 힙에 push
    • 반복이 종료되면 c[e]를 반환
  • 그래프 생성: G := n+1개의 빈 리스트로 초기화하고, edges의 각 항목 (u, v, w)에 대해 G[u]에 (v, w)를, G[v]에 (u, w)를 추가합니다. 무방향 그래프이므로 양방향으로 등록해야 합니다.
  • 결과 반환: ans := helper(G, s, e)를 호출한 뒤, ans가 무한대와 같으면 -1을, 그렇지 않으면 ans를 반환합니다.

구현 코드

더 나은 이해를 위해 다음 파이썬 구현을 살펴보겠습니다.

import heapq
from math import inf

def helper(G, s, e):
    v = set()
    c = [inf] * len(G)
    heap = [(0, s)]
    while len(heap) > 0:
        cst, cur = heapq.heappop(heap)
        c[cur] = min(cst, c[cur])
        if (cst, cur) in v:
            continue
        if cur == e:
            return c[cur]
        v.add((cst, cur))
        for neighbor, n_cost in G[cur]:
            heapq.heappush(heap, (n_cost | cst, neighbor))
    return c[e]

def solve(n, edges, s, e):
    G = [[] for _ in range(n + 1)]
    for item in edges:
        u, v, w = map(int, item)
        G[u].append((v, w))
        G[v].append((u, w))
    ans = helper(G, s, e)
    return -1 if ans == inf else ans

print(solve(4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3))

입력 및 출력

입력

4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3

출력

15

마무리

이 알고리즘은 최소 힙을 사용해 현재까지의 누적 OR 값이 가장 작은 상태부터 탐색하기 때문에, 목표 정점에 처음 도달했을 때의 값이 곧 최소 페널티가 됩니다. 각 정점에서 도달 가능한 서로 다른 OR 누적값의 수는 간선 가중치의 비트 폭에 의해 제한되므로, 상태 공간이 관리 가능한 크기를 유지하며 실제 그래프 문제에서도 효율적으로 동작합니다.