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

Python 백트래킹으로 그래프에서 길이가 k보다 긴 단순 경로 찾기

문제 정의

그래프 하나와 시작 정점(source), 그리고 숫자 k가 주어졌다고 가정해 보겠습니다. 여기서 k는 시작 정점에서 목적지까지 도달해야 하는 경로 길이를 의미합니다. 우리가 확인해야 할 것은, 시작 정점에서 출발하여 다른 임의의 정점에서 끝나는 사이클이 없는 단순 경로(simple path) 중 총 길이가 k보다 긴 것이 존재하는지 여부입니다.

Python 백트래킹으로 그래프에서 길이가 k보다 긴 단순 경로 찾기

예를 들어 Source = 0, k = 64가 입력으로 주어진다면 결과는 True입니다. 0 → 7 → 1 → 2 → 8 → 6 → 5 → 3 → 4로 이어지는 단순 경로가 존재하고, 이 경로의 총 가중치 합은 68로 64보다 크기 때문입니다.

해결 전략: 백트래킹(Backtracking)

이 문제는 백트래킹 기법을 적용한 깊이 우선 탐색(DFS)으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 현재 정점에서 인접한 정점들을 하나씩 방문해 봅니다.
  • 이미 방문한 정점은 다시 방문하지 않아 단순 경로를 유지합니다.
  • 간선의 가중치 w가 남은 필요 거리 k보다 크거나 같으면 즉시 성공(True)을 반환합니다.
  • 탐색에 실패하면 방문 표시를 되돌려(백트래킹) 다른 경로를 계속 시도합니다.

알고리즘 단계

  1. 인접 리스트 adj를 사용해 그래프를 정의하고, 각 간선의 가중치를 함께 저장합니다.
  2. solve(source, k, path) 함수를 정의합니다.
  3. k <= 0이면 True를 반환합니다. 이미 요구 길이를 충족했다는 의미입니다.
  4. i를 0으로 초기화하고, i가 adj[source]의 길이와 같아질 때까지 아래 과정을 반복합니다.
    • v := adj[source][i][0], w := adj[source][i][1]로 인접 정점과 가중치를 가져온 뒤 i를 1 증가시킵니다.
    • path[v]가 True라면 이미 방문한 정점이므로 건너뜁니다.
    • w >= k라면 현재 간선만으로 조건을 만족하므로 True를 반환합니다.
    • path[v]를 True로 표시한 후 solve(v, k - w, path)를 재귀 호출합니다. 결과가 True면 True를 반환합니다.
    • 실패했다면 path[v]를 False로 되돌립니다(백트래킹).
  5. 모든 인접 정점을 확인했는데도 성공하지 못하면 False를 반환합니다.

메인 함수 처리 흐름

  • 노드 수와 같은 크기의 path 리스트를 만들고 모두 False로 초기화합니다.
  • path[source]를 True로 설정해 시작 정점을 방문 처리합니다.
  • solve(source, k, path)의 결과를 반환합니다.

Python 구현 예제

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj = [[] for i in range(nodes)]

    def insert_edge(self, u, v, w):
        self.adj[u].append([v, w])
        self.adj[v].append([u, w])

    def solve(self, source, k, path):
        if (k <= 0):
            return True
        i = 0
        while i != len(self.adj[source]):
            v = self.adj[source][i][0]
            w = self.adj[source][i][1]
            i += 1
            if (path[v] == True):
                continue
            if (w >= k):
                return True
            path[v] = True
            if (self.solve(v, k-w, path)):
                return True
            path[v] = False
        return False

    def is_there_any_path(self, source, k):
        path = [False]*self.nodes
        path[source] = 1
        return self.solve(source, k, path)

nodes = 9
g = Graph(nodes)
g.insert_edge(0, 1, 5)
g.insert_edge(0, 7, 9)
g.insert_edge(1, 2, 9)
g.insert_edge(1, 7, 12)
g.insert_edge(2, 3, 8)
g.insert_edge(2, 8, 3)
g.insert_edge(2, 5, 5)
g.insert_edge(3, 4, 10)
g.insert_edge(3, 5, 15)
g.insert_edge(4, 5, 11)
g.insert_edge(5, 6, 3)
g.insert_edge(6, 7, 2)
g.insert_edge(6, 8, 7)
g.insert_edge(7, 8, 8)

source = 0
k = 64
print(g.is_there_any_path(source, k))

입력

source = 0
k = 64

출력

True

복잡도 분석

최악의 경우 이 알고리즘은 그래프에 존재하는 모든 단순 경로를 탐색해야 하므로 시간 복잡도는 지수형(exponential)에 가깝습니다. 실제로 '길이가 k 이상인 단순 경로의 존재 여부'를 판단하는 문제는 최장 경로(longest path) 문제와 밀접하게 관련된 NP-난해(NP-hard) 문제로 알려져 있어, 다항 시간에 해결하는 일반적인 방법은 알려져 있지 않습니다. 따라서 백트래킹과 가지치기를 활용한 완전 탐색이 현실적인 접근 방식입니다.