[BOJ][Python]1738 풀이

https://www.acmicpc.net/problem/1738

1738번: 골목길

import sys
ssr = sys.stdin.readline

INF = 987654321

def bellman_ford():
    for i in range(1, n+1):
        for cur_node, next_node, next_cost in edges:
            cost = max_cost[cur_node] + next_cost
            if max_cost[cur_node] != -INF and cost > max_cost[next_node]:
                max_cost[next_node] = cost
                routes[next_node] = cur_node
                if i == n:
                    max_cost[next_node] = INF
    
def find(node):
    if routes[node] != node:
        if max_cost[node] == INF:
            ans.append(-1)
            return
        else:
            find(routes[node])
    return ans.append(node)
                    
n, m = map(int, ssr().split())
edges = [list(map(int, ssr().split())) for _ in range(m)]
routes = [i for i in range(n+1)]
max_cost = [-INF for _ in range(n+1)]
max_cost[1] = 0
bellman_ford()
ans = []
find(n)
if -1 in ans:
    print(-1)
else:
    print(*ans)

이번에도 벨만 포드입니다. 익숙해지려고 하나 더 간단하게 풀려고 했는데 벨만 포드 이외의 부분에서 좀 고민을 많이 했네요.

 

일단 경로를 출력하는걸 처음해봐서 약간 헤맸는데, 유니온 파인드 하듯이 부모 노드를 저장해두면 마지막으로 가면 되겠더라구요. 자식 노드를 저장하는 것도 생각해봤는데 실제 최단 경로에 포함이 안될 가능성이 있어서 부모 노드를 저장했다가 나중에 재귀로 찾는게 맞겠더라구요.

 

그리고 단순히 사이클이 있고 없고만 판단하는게 아니라 사이클이 있어도 최적의 경로가 있는 경우가 있어서 해당 부분을 체크해줘야 합니다. 처음에는 사이클을 구성하는 원소들을 전부 다 담아서 경로를 찾아나갈 때 사이클에 포함된 노드가 있으면 -1을 출력하는 방식을 썼는데, 다른 분들 코드를 보니까 n번을 넘어서 갱신이 될 때 해당 노드를 INF로 초기화 하면 굳이 조건문을 복잡하게 짤 필요도 사이클 배열을 따로 만들 필요도 없더라구요. 똑똑한 사람들이 많네요.

 

그 외에는 기본적인 벨만 포드에서 크게 다른 부분은 없었습니다만, 이상하게 저는 이 문제를 푸는데 고민도 정말 많이 하고 시간도 많이 걸렸네요. 그리고 오늘은 solvedac grand arena에 참여 해봤는데 대차게 망했습니다. 1번은 간단하게 풀었는데 뭘 잘못했는지 b d e에서 계속 런타임 에러가 나는데 아무리 코드를 봐도 런타임 에러가 날만한 부분은 인덱스 에러인 것 같은데 제가 생각해낼 수 있는 많은 예시를 시도해봤는데 런타임 에러가 나질 않더라구요. 그래서 어차피 망했다 싶어서 내내 런타임 에러를 잡아보려고 했는데 결국 시간내에 못풀고 그냥 1솔로 마무리했습니다. 착잡하네요. 다음 주에도 한 번 더 있던데 참여할지 말지 고민입니다.