[백준]1219 오민식의고민

1.풀이

(1) 목적지에서 벌수있는 돈을 음(-)으로, 이동비용을 (+)로 두고 간선의 가중치를 부여한다

(2) 벨만포드로 최단 거리를 구하기 위해 N-1번 edge relaxation 수행한다.

(3) N번째에서 아래의 사항을 확인

- 음의 사이클이 있는지(nodeCost[n1]+cost<nodeCost[n2] )

- 시작부분과 연결된 음의 사이클인지(nodeCost[n1]!=maxNum)

- 목적지와도 연결이 되어있는지 (bfs) 로 확인한다.

(4) 다음의 경우의 수를 판단한다

- 목적지까지 도달하지 못하는경우 ->"gg"

- (시작부분과 연결된)음의사이클이 존재하고, 해당 음의 사이클에서 목적지로 이동이가능할때(bfs로확인)->"gee"

- 그렇지않은경우(목적지까지 도달할수있고, 음의사이클이 존재하지만 목적지로 도달할수 없는경우 or 음의사이클 존재안하는경우) -> 값출력 (-1곱할것)

​

*많이틀림

처음에 출발지에서 임의의 음의 싸이클까지 연결이 되있는지를 확인해주는 N번째반복의 조건문(nodeCost[n1]!=maxNum)를 빼트리고 음의 싸이클이 있는지만 확인해줘서 한참 틀렸다. 소스코드1 ​처럼하면 임의의 사이클에서 목적지까지 연결되어있는지만 확인이 되지, 출발지에서 임의의 사이클까지 연결이 되어있는것은 보장되지 않는다. 따라서 틀렸다.

​

2.소스코드

(1) 소스코드1 (출발지에서 음의싸이클사이 연결확인x)

from collections import deque
maxNum=9999999999999999

def bellman():
    nodeCost=[maxNum for i in range(N)]
    nodeCost[A]=-money[A]
    #벨만포드
    for i in range(N-1):
        for n1,n2,cost in edge:
            if nodeCost[n1]==maxNum:
                continue
            nowCost=nodeCost[n1]+cost
            if nowCost<nodeCost[n2]:
                nodeCost[n2]=nowCost

    isUpdate=False
    isPossible=False
    #싸이클있는지 확인
    for n1,n2,cost in edge:
        #시작부분와 연결되어있는지 확인해주는 nodeCost[n1]!=maxNum 조건이 빠짐
        if nodeCost[n1]+cost<nodeCost[n2]:
            #print(n1,n2,"사이클확인시작")
            isUpdate=True
            #싸이클에서 목적지 갈 수 잇는지 확인
            visited=[-1 for i in range(N)]
            q=deque([n1])
            visited[n1]=1
            while(q):
                temp=q.popleft()
                if temp==B:
                    isPossible=True
                    break
                for node in graph[temp]:
                    if visited[node]==-1:
                        visited[node]=1
                        q.append(node)
            break
    #print(isUpdate,isPossible)
    #print(nodeCost)
    #도달여부확인
    if nodeCost[B]==maxNum:
        print("gg")
    else:
        if isUpdate and isPossible:
            print("Gee")
        else:
            print(-nodeCost[B])
    return

N,A,B,M=map(int,input().split())
edge=[]
graph={}
for i in range(N):
    graph[i]=[]
for m in range(M):
    temp=list(map(int,input().split()))
    edge.append(temp)
    graph[temp[0]].append(temp[1])

money=list(map(int,input().split()))

#방문했을때 버는 돈 추가
for m in range(M):
    edge[m][2]-=money[edge[m][1]]
bellman()

 

(2) 소스코드2 (정답)

from collections import deque
maxNum=9999999999999999

def bellman():
    nodeCost=[maxNum for i in range(N)]
    nodeCost[A]=-money[A]
    #벨만포드
    for i in range(N-1):
        for n1,n2,cost in edge:
            if nodeCost[n1]==maxNum:
                continue
            nowCost=nodeCost[n1]+cost
            if nowCost<nodeCost[n2]:
                nodeCost[n2]=nowCost

    isUpdate=False
    isPossible=False
    #싸이클있는지 확인(N번째 반복)
    for n1,n2,cost in edge:
        #시작부분과 연결되었고, 음의 사이클이 존재할때
        if nodeCost[n1]!=maxNum and nodeCost[n1]+cost<nodeCost[n2]:
            #print(n1,n2,"사이클확인시작")
            isUpdate=True
            #싸이클에서 목적지 갈 수 잇는지 확인
            visited=[-1 for i in range(N)]
            q=deque([n1])
            visited[n1]=1
            while(q):
                temp=q.popleft()
                if temp==B:
                    isPossible=True
                    break
                for node in graph[temp]:
                    if visited[node]==-1:
                        visited[node]=1
                        q.append(node)
            if isPossible:
                break
    #print(isUpdate,isPossible)
    #print(nodeCost)
    #도달여부확인
    if nodeCost[B]==maxNum:
        print("gg")
    else:
        if isUpdate and isPossible:
            print("Gee")
        else:
            print(-nodeCost[B])


N,A,B,M=map(int,input().split())
edge=[]
graph={}
for i in range(N):
    graph[i]=[]
for m in range(M):
    temp=list(map(int,input().split()))
    edge.append(temp)
    graph[temp[0]].append(temp[1])
money=list(map(int,input().split()))
#방문했을때 버는 돈 추가
for m in range(M):
    edge[m][2]-=money[edge[m][1]]
bellman()