[Python] 1738. 골목길(골1) / 벨만-포드 알고리즘

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

1738번: 골목길

---

2. 핵심 아이디어

 

최근 백준 단기간 성장 문제집을 풀고 있다.

 

그중 타임머신이란 문제를 풀게 되었는데

이 문제가 벨만-포드 알고리즘과 연관이 있었다.

 

다익스트라나 플로이드는 익숙해도

가중치가 음수인 그래프를 다루는 벨만-포드는 익숙치 않아

이런 저런 문제를 찾아 풀고 있다

 

본 풀이는 벨만-포드 알고리즘을 이해하고 있다는 전제하여

아이디어를 설명한다.

 

그러니, 먼저 벨만-포드에 대해 알아보자

[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

 

 

골목길 문제가 어렵게 느껴지는 이유는 다음과 같다.

1. 최소거리를 구하는 문제가 아니다. => 최대거리를 구하는 문제이다.

2. 비용이 아닌 경로를 출력해야 한다.

3. 최적의 경로가 존재하지 않는 상황을 고려해야 한다.

 

 

그럼 하나씩 이게 무엇을 의미하는지 살펴보자

---

1.  최대거리를 구하는 문제이다.

이 문제에서 최적의 거리란 다음을 의미한다.

최적의 경로는 민승이네 집에서 출발하여 코레스코 콘도에 도착하는 경로 중
금품의 양이 최대가 되는 경로이다.

 

그동안 벨만 포드 알고리즘을 생각할 때는

가중치를 비용으로 생각했다.

 

그러나, 이번문제는 가중치의 합이 최대가 되는 경로

즉 가중치로 해석하는 금품의 양이 많은 경로를 추적해야 한다. 

 

따라서 일반적인 bellman ford가 비용이 더 적을 때 갱신해주는 한편,

distance[next_node] > distance[cur_node]+next_cost

 

이번에는 비용이 더 커질때 갱신해주어야 한다.

distance[next_node] < distance[cur_node]+next_cost

 

그렇기에 각 노드까지 이르는 거리를 나타내는 distance 배열도

-INF로 초기화해주어야 한다.

 

---

2.  비용이 아닌 경로를 출력해야 한다.

경로 출력을 위해 간선이 갱신될 때마다 next_node란에 이전 노드를 갱신한다.

이는 다익스트라에서 이전 노드를 갱신하며 경로를 추적하는 과정과 같다.

출처 : http://www.gisdeveloper.co.kr/?p=3881

 

예를 들어 위의 노드에서 0에서 4로 가는 최소거리 경로는 다음 과 같다.

0-3-5-6-4 

 

그렇기에 T배열을 살펴보면

4 => 6

6=> 5

5=> 3

3=> 0

 

처럼 각 경로의 이전 노드를 기록하여 경로를 추적할 수 있도록 해놓았다.

 

이것을 그대로 적용하여 경로가 추적가능하게 만들면 된다.

 

---

3.  최적의 경로가 존재하지 않는 상황을 고려해야 한다.

우선 벨만포드 알고리즘에서 웬만한 예외상황은 음의 사이클이 나오는 상황이다.

 

음의 사이클이란?

 

그런데 이 문제에서는 음의 사이클이 존재해도 

답이 존재하는 상황이 발생한다.

 

최소 비용이 아닌 최대 비용을 생각하는 문제이기 때문에

음의 사이클이 존재하도 이 사이클을 비껴갈 수 있는 경로가 있다면

분명 유일한 경로가 존재할 수 있기 때문이다.

 

예를 들어 다음상황을 보자

출처 : https://4legs-study.tistory.com/26

 

다음 그래프에는 음의 사이클이 존재한다.

 

그러나, 1에서 5로 가는 최적경로가 존재한다.

1-5로 100개의 금품을 얻고 가면 되기 때문이다.

 

따라서, 이번 문제에서 최적의 경로가 없는 상황은

음의 사이클의 존재 자체가 아니라

음의 사이클에 코레스코 콘도 노드(n번째) 노드가 속하는 상황이 된다.

 

 

따라서, 만약 node가 음의 사이클이 있다면

distance[next_node] 를 INF로 갱신하고

 

만약 distance[n]==INF라면, 음의 사이클 중에 n번째 노드가 속한다는 것이므로

-1을 출력하는 식으로 예외상황을 고려해주면 된다.

 

---

그외 여러 고려사안

 

-- edges 배열에 받아주었더니 => 메모리 초과

=> graph 의 2차원 배열로 수정

=> 배열을 지역변수로 선언

 

<기존 코드>

for _ in range(m):
  a,b,c= map(int, input().split())
  edges.append((a,b,c))

def bellman(start):
  distance[start]=0
  for j in range(n):
    for i in range(m):
      cur_node= edges[i][0]
      next_node= edges[i][1]
      next_cost= edges[i][2]

 

<수정 코드> => 지역변수로 선언해 stack 영역에 담아줌

n,m= map(int, input().split())

graph=[[] for _ in range(n+1)]

for _ in range(m):
  a,b,c= map(int, input().split())
  graph[a].append((b,c))
  
def bellman(start):
  global n
  distance = [-INF]*(n+1) # 최대거리를 찾으므로 -INF로 초기화
  distance[start]=0
  route= [0]*(n+1)
  result=[]

  for i in range(n):
    for cur_node in range(1, n+1):
      if distance[cur_node]==-INF:
          continue

      for next_node, next_cost in graph[cur_node]:
        
        if distance[next_node]<distance[cur_node]+next_cost: #비용이 더 커지면 갱신
          distance[next_node]=distance[cur_node]+next_cost 
          route[next_node]=cur_node
          if i==n-1:
            distance[next_node]=INF

 

 

-- 재귀를 경로 추적 알고리즘 => recursion

=> 반복문으로 수정

 

<기존 코드>

#재귀를 통해 route 찾기 => 반복문으로 대체
def find_route(n):
  if n==1:
    result.append(n)
    return
  else:
    result.append(n)
    return find_route(route[n])

 

<수정 코드> => 반복문으로 돌려 recursionlimit 고려요소를 없애줌

 while(n!=1):
      result.append(route[n])
      n= route[n]

---

3. 코드

# 벨만포드 - #1738. 골목길(골1)
#사이클이 있다고 무조건 -1이 아니라, 도착지에 사이클이 생기면 -1 불가능

import sys

INF= sys.maxsize

def bellman(start):
  global n
  distance = [-INF]*(n+1) # 최대거리를 찾으므로 -INF로 초기화
  distance[start]=0
  route= [0]*(n+1)
  result=[]

  for i in range(n):
    for cur_node in range(1, n+1):
      if distance[cur_node]==-INF:
          continue

      for next_node, next_cost in graph[cur_node]:
        
        if distance[next_node]<distance[cur_node]+next_cost: #비용이 더 커지면 갱신
          distance[next_node]=distance[cur_node]+next_cost 
          route[next_node]=cur_node # 이전 노드 갱신
          if i==n-1:
            distance[next_node]=INF  # 음의 사이클이라면 INF로 갱신됨
  
  if distance[n]==INF: #음의 사이클 경로에 목적지도 포함된다면 => -1 출력
    print(-1)
    return
  else:
    result.append(n)
    while(n!=1):
      result.append(route[n])
      n= route[n]
    
    result.reverse()
    print(*result)
    return


n,m= map(int, input().split())

graph=[[] for _ in range(n+1)]

for _ in range(m):
  a,b,c= map(int, input().split())
  graph[a].append((b,c))


bellman(1)

---

4. 배운 점

우선 벨만 포드 알고리즘에 대해 조금 깊이 있는 이해를 할 수 있었다.

음수 간선이 나오는 그래프에서 최대 경로를 찾다보니까 기존에 관습적으로 짰던 코드들

 

ex) distance를 INF로 초기화했던 것들 / 음의 사이클 존재하면 경로가 없다고 생각했던 것들

의 의미를 되새기고 제대로 이해할 수 있었다.

 

특히, 메모리 초과가 뜰 때 아예 변수나 배열 선언을 함수 내로 편입하여 메모리 관리를 하는 것이나

edges를 2차원배열로 선언하는 등의 미묘한 부분이 매우 큰 영향을 줄 수 있음을 알았다.

 

또한, 재귀문과 반복문 중 되도록 반복문으로 코드를 짜는게 더 편하다는 생각도 했다..

재귀는 직관적이지만 오버헤드도 많이 발생하고 효율적이지 않은 것 같다.