(Python/🥈1)백준리즘알고즘 4883번 : 삼각 그래프

 

문제 바로가기 

문제:

이 문제는 삼각 그래프의 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최단 경로를 찾는 문제이다. 삼각 그래프는 사이클이 없는 그래프로 N ≥ 2 개의 행과 3열로 이루어져 있다. 삼각 그래프는 보통 그래프와 다르게 간선이 아닌 정점에 비용이 있다. 어떤 경로의 비용은 그 경로에서 지나간 정점의 비용의 합이다. 오른쪽 그림은 N = 4인 삼각 그래프이고, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 경로 중 아래로만 가는 경로의 비용은 7+13+3+6 = 29가 된다. 삼각 그래프의 간선은 항상 오른쪽 그림과 같은 형태로 연결되어 있다.

입력:

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

출력:

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

 

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
count = 1
while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    graph = [list(map(int, sys.stdin.readline().split(" "))) for _ in range(n)]
    dp = [[0] * 3 for _ in range(n + 1)]
    dp[1][0] = graph[1][0] + graph[0][1]  # 좌대각
    dp[1][1] = graph[1][1] + min(dp[1][0], graph[0][1], graph[0][2] + graph[0][1])  # 바로내려오기, 오아
    dp[1][2] = graph[1][2] + min(dp[1][1], graph[0][1], graph[0][1] + graph[0][2])  # 바로내려오기, 오아
    # print(dp)
    if n >= 2:
        for i in range(2, n):
            dp[i][0] = graph[i][0] + min(dp[i - 1][0], dp[i - 1][1])
            dp[i][1] = graph[i][1] + min(dp[i][0], dp[i - 1][0], dp[i - 1][1], dp[i - 1][2])
            dp[i][2] = graph[i][2] + min(dp[i][1], dp[i - 1][1], dp[i - 1][2])
    print(count, dp[-2][1], sep=". ")
    count += 1

 

각 위치 별로 올 수 있는 최소값을 저장한다.

 

근데 바로 음수값이 올 수 있어

바로 오는것보다 조금 돌아서 오는것까지 체크해주면된다.

 

3
1 1 1
1 1 1
-1 1 1
0

 

예를들어 이런 케이스를 생각해보면 된다.