[파이썬] 1738 골목길 (백준)

1. 문제 설명

문제 : 1738 - 골목길 https://www.acmicpc.net/problem/1738

사용 언어 : 파이썬 (Pypy3)

 

문제요약 :

각 거리마다 얻거나, 빼앗길 수 있는 금품의 양이 주어졌을 때, 최대의 금품을 갖게 될 수 있는 경로를 구하여라.

 

알고리즘 : 벨만-포드

---

2. 문제 풀이

해설 :

일반적인 벨만포드를 이용하여 구할 수 있다.

이때 고려해야 할 점이 몇 가지 있다.

 

1. 최소 가중치를 찾는 벨만포드와는 다르게, 최대 가중치를 구해야 하므로 distance를 -inf로 초기화해야 한다. (이에 따라 조건식을 조금 바꾸어야 한다.)

2. 중요한 경로 구하기!! 각 노드마다 그 전의 노드를 구해놓아 마지막에 최단 경로를 구한다.

 

코드 :

import sys; input = sys.stdin.readline
INF = int(1e9)

def BellmanFord(start):
    distance[start] = 0

    for i in range(N):
        for j in range(M):
            now_node, next_node, cost = road[j][0], road[j][1], road[j][2]

            if distance[now_node] != -INF and distance[next_node] < distance[now_node]+cost:
                distance[next_node] = distance[now_node]+cost
                route[next_node] = now_node # 경로 구하기 위해 선작업

                if i == N-1:
                    distance[next_node] = INF



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

distance = [-INF for i in range(N+1)] # -inf (최대 가중치)
route = [0 for i in range(N+1)]
road = []

for i in range(M):
    road.append(list(map(int,input().rstrip().split())))

BellmanFord(1)

result = [N]
if distance[N] != INF:
    node = N
	
    # 경로 구하기
    while node != 1:
        node = route[node]
        result.append(node)

    result.reverse()
    print(*result)

else: print(-1)

---

앞으로 코딩과 알고리즘 관련 글을 업로드할 예정입니다!

아직 배우는 중이라서 부족한 점이 있으면 댓글 남겨주시면 감사하겠습니다!!