[백준]1738 골목길

1. 풀이

(1) 벨만포드를 적용할 때 경로를 저장한다.

* 처음엔 특정 노드에서 어디로 가는지를 저장했다. 하지만 이렇게 하면 우리가 원하는 목적지로 가는 경로가 나오는것이 아니라 입력 순서에 영향을 받아 해당 노드에서 어떠한 다른 노드로의 최단경로의 일부가 저장될 수 있다.

ex) 1-2, 1,3이 있고 3이 목적지일때 1노드의 방향이 2노드를 향할 수 있다.

따라서 특정 노드가 어느 노드에서 오는지를 저장해야한다. (즉 이전 노드가 무엇인지를)

​

(2) 벨만 포드를 적용한 후 싸이클을 확인해야한다. 이때 경우의 수는 다음과 같다

<경우의수>

1. (출발지에 붙은)사이클이 있다 (​isUpdate==True)

  (1) 도착지와 붙어있다. (q를 통해서 확인, connectCycle==True) => -1

  (2) 도착지와 붙어있지 않다. (connectCycle==False) => 답구해

2. 싸이클이 없다 (isUpdate==False)

  (1) 도달불가능. (nodeDist[nodwNode][1]==minNum : nodeDist가 갱신되지않음) => -1

  (2) 도달가능. => 답구해

* 싸이클이 있어도 싸이클에서 도착지로 가지 못하면 경로가 있는것이기 때문에 q를 통해 확인해주어야 한다.

​

2. 소스코드

from collections import deque

minNum=-9876543210
n,m=map(int,input().split())
edge=[]
graph={}
for i in range(1,n+1):
    graph[i]=[]
for i in range(m):
    a,b,c=map(int,input().split())
    edge.append([a,b,c])
    graph[a].append(b)

# [이전노드, ost]
nodeDist=[[i,minNum] for i in range(n+1)]
nodeDist[1][1]=0
def ans():
    ans = []
    now = n
    while (now != 1):
        ans.append(now)
        now = nodeDist[now][0]
    ans.append(now)
    print(*list(reversed(ans)))


def bellman():
    for i in range(n-1):
        for nowNode,toNode,cost in edge:
            if nodeDist[nowNode][1]==minNum:
                continue
            nowDist=nodeDist[nowNode][1] + cost
            if nowDist>nodeDist[toNode][1]:
                nodeDist[toNode][1]=nowDist
                nodeDist[toNode][0]=nowNode

    #싸이클이 있고, 싸이클이 도착지와 연결되는가?
    connectCycle=False
    isUpdate=False
    for nowNode,toNode,cost in edge:
        #출발지와 연결된 싸이클만
        if nodeDist[nowNode][1]==minNum:
            continue
        else:
            nowDist=nodeDist[nowNode][1]+cost
            if nowDist>nodeDist[toNode][1]:
                isUpdate=True
                q=deque([nowNode])
                visited=[-1 for i in range(n+1)]
                visited[nowNode]=1
                while(q):
                    temp=q.popleft()
                    #싸이클이 목적지와 붙어있다
                    if temp==n:
                        connectCycle=True
                        break
                    for conNode in graph[temp]:
                        if visited[conNode]==-1:
                            visited[conNode]=1
                            q.append(conNode)
    #(출발지와 붙은)싸이클있다
    if isUpdate:
        #도착지와도 붙어있다
        if connectCycle:
            print(-1)
        else:
            ans()
    else:
        #도달불가능
        if nodeDist[n][1]==minNum:
            print(-1)
        #도달가능
        else:
            ans()

bellman()