[Python] 1738 골목길

[Platinum V] 골목길 - 1738 

[문제 링크](https://www.acmicpc.net/problem/1738)

---

💻 문제 정의

민승이가 집에서부터 콘도까지 가기 위해 골목길을 지나야 한다. 각 골목길에는 강도가 있어 금품을 갈취 당하거나 획득할 수 있다. 최적의 경로로 이동하여 금품의 양이 최대가 되는 경로를 출력하는 문제이다.

💡 접근 및 설계

금품을 잃거나 획득할 수 있기 때문에 간선의 이동 비용이 음수도 존재할 수 있다. 음수 간선이 존재하기에 벨만-포드 최단거리 알고리즘을 활용하였다.

✏️ 알고리즘 풀이

distance = [-INF] * (N+1) # 각 노드별로 거리 저장 리스트
route = [0 for _ in range(N+1)] # 현재 노드에서 이어진 다음 노드
edges = [] # 간선 저장 리스트

def bellman_ford(start):
    distance[start] = 0 # 시작 지점의 이동 거리는 0

    for i in range(N):
        for j in range(M):
            curr_node = edges[j][0] # 현재 노드
            next_node = edges[j][1] # 다음 노드
            edge_cost = edges[j][2] # 그때의 비용

            # 현재 노드가 순환 사이클에 존재하지 않고, 다음 노드로 이동하는 비용이 더 크다면,
            if distance[curr_node] != -INF and distance[next_node] < distance[curr_node] + edge_cost:
                distance[next_node] = distance[curr_node] + edge_cost
                route[next_node] = curr_node # 현재 노드로 오기 위해서 이전 노드의 정보를 저장한다.

                # 순환 사이클 발생
                if i == N-1:
                    distance[next_node] = INF

벨만-포드 함수이다. 현재 노드에서 다음 노드로 이동할 때, 비용이 가장 높은 방향으로 이동한다. 그리고 해당 노드로 이동한 것을 route에 저장한다.

# 경로 역추적
result = [N]
if distance[N] != INF:
    node = N

    # 1번 노드까지 도달할 때 까지
    while node != 1:
        node = route[node] # 현재 노드에서 이전 노드로 역추적
        result.append(node) # result에 저장

    result.reverse() # 역방향이기에 뒤집고
    print(*result) # 출력

# 마지막 지점에서 비용이 무한대라면 -1 출력
else:
    print(-1)

벨만-포드로 최적의 경로를 찾으면서 동시에 route에 이동 경로를 저장하였기에 이를 역추적하며 원래 진행 방향대로 되돌리는 과정을 거쳐야 한다. N번 노드부터 1번 노드까지 역으로 이동하며 저장한 후, 뒤집어서 출력한다. 만약 마지막 지점까지 가는 비용이 INF라면 해당 트리는 사이클이 존재하는 구조로 최적의 경로를 찾을 수 없는 구조이다. 따라서 -1을 출력한다.

🗒️ 최종 제출 코드

# 1738 골목길

INF = 1_000_000_000

def bellman_ford(start):
    distance[start] = 0 # 시작 지점의 이동 거리는 0

    for i in range(N):
        for j in range(M):
            curr_node = edges[j][0] # 현재 노드
            next_node = edges[j][1] # 다음 노드
            edge_cost = edges[j][2] # 그때의 비용

            # 현재 노드가 순환 사이클에 존재하지 않고, 다음 노드로 이동하는 비용이 더 크다면,
            if distance[curr_node] != -INF and distance[next_node] < distance[curr_node] + edge_cost:
                distance[next_node] = distance[curr_node] + edge_cost
                route[next_node] = curr_node # 현재 노드로 오기 위해서 이전 노드의 정보를 저장한다.

                # 순환 사이클 발생
                if i == N-1:
                    distance[next_node] = INF

N, M = map(int, input().split())

distance = [-INF] * (N+1) # 각 노드별로 거리 저장 리스트
route = [0 for _ in range(N+1)] # 현재 노드에서 이어진 다음 노드
edges = [] # 간선 저장 리스트
for _ in range(M):
    a, b, weight = map(int, input().split())
    edges.append([a, b, weight])

bellman_ford(1) # 1번 노드부터 출발

# 경로 역추적
result = [N]
if distance[N] != INF:
    node = N

    # 1번 노드까지 도달할 때 까지
    while node != 1:
        node = route[node] # 현재 노드에서 이전 노드로 역추적
        result.append(node) # result에 저장

    result.reverse() # 역방향이기에 뒤집고
    print(*result) # 출력

# 마지막 지점에서 비용이 무한대라면 -1 출력
else:
    print(-1)

---

💭 오늘의 회고

두 번째 플레티넘 문제다. 벨만-포드 최단경로 알고리즘은 큰 어려움 없이 구현 하였으나, 이를 어떻게 활용해서 최적의 경로를 구할지는 생각하기 어려웠다. 벨만-포드 함수 자체가 최단 경로로 이동하는 최적의 비용을 계산하는 알고리즘이다보니 방법을 떠올리기 쉽지 않았다.

최적의 경로를 찾아가는 과정을 모두 기록한 후, 역방향으로 다시 돌아가며 최종적으로 정방향을 찾아낸다는 아이디어가 참신했다.