[백준/4883] 삼각 그래프 (Python)

Problem : https://www.acmicpc.net/problem/4883

4883번: 삼각 그래프

 

Difficulty : Silver 1

 

Status :Solved

 

Time : 00:08:14

 

---

 

문제 설명

 

이 문제는 삼각 그래프의 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최단 경로를 찾는 문제이다.

삼각 그래프는 사이클이 없는 그래프로 N ≥ 2 개의 행과 3열로 이루어져 있다. 삼각 그래프는 보통 그래프와 다르게 간선이 아닌 정점에 비용이 있다. 어떤 경로의 비용은 그 경로에서 지나간 정점의 비용의 합이다.

오른쪽 그림은 N = 4인 삼각 그래프이고, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 경로 중 아래로만 가는 경로의 비용은 7+13+3+6 = 29가 된다. 삼각 그래프의 간선은 항상 오른쪽 그림과 같은 형태로 연결되어 있다.

 

 

입력 및 출력

 

입력

 

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 순서대로 주어진다. 비용은 정수이며, 비용의 제곱은 1,000,000보다 작다.

입력의 마지막 줄에는 0이 하나 주어진다.

 

출력

 

각 테스트 케이스에 대해서, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최소 비용을 테스트 케이스 번호와 아래와 같은 형식으로 출력한다.

k. n

k는 테스트 케이스 번호, n은 최소 비용이다.
 

입력 예시

 

4
13 7 5
7 13 6
14 3 12
15 6 16
0

 

출력 예시

 

1. 22

 

 

---

 

풀이

 

이 그래프의 특징을 생각해보자.

 

• 이 그래프는 사이클을 생성하지 않는다. 이는 중요하다. 어떤 노드에 도달하기 위해선 무조건 이전 노드를 거쳐야 하며, 이전 노드로 돌아갈 방법이 없다. 한 그래프의 노드 좌표를 (x, y)로 생각한다면 (x-1, y-1), (x-1, y), (x, y-1), (x+1, y-1) 노드가 이 노드에 영향을 줄 수 있고, 반대로 이 노드는 (x+1, y), (x-1, y+1), (x, y+1), (x+1, y+1) 노드에 영향을 줄 수 있다.
• 따라서 이 그래프의 처음 정점에서 끝 정점까지의 최적해는 각 노드의 부분해를 모두 포함한다. 즉 DP를 수행 가능하다.

DP를 사용할 경우 (x, y)좌표의 DP는 (x, y)좌표의 노드값 + 이전 노드의 dp값 중 최솟값으로 구성된다. 이를 모든 노드에 대해 수행하면 되므로 시간복잡도는 O(N)이 된다.

 

 

풀이 코드

 

import sys
input = sys.stdin.readline
px = [-1, -1, 0, 1]
py = [0, -1, -1, -1]
MAX = float('inf')
cnt = 1
while True :
  N = int(input())
  if N == 0 :
    break
  node_list = [list(map(int, input().split())) for _ in range(N)]
  
  dp = [[MAX]*3 for _ in range(N)]
  dp[0][1] = node_list[0][1]
  dp[0][2] = node_list[0][1] + node_list[0][2]
  
  for i in range(1, N) :
    for j in range(3) :
      min_val = MAX
      for k in range(4) :
        ai, aj = i+py[k], j+px[k]
        if -1 < aj < 3 and min_val > dp[ai][aj] :
          min_val = dp[ai][aj]
      dp[i][j] = node_list[i][j] + min_val
  
  print("{:d}. {:d}".format(cnt, dp[-1][1]))
  cnt += 1

풀이 완료!