백준 4883 [삼각 그래프] 파이썬

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

 

import sys

k = 0  # 테스트 케이스 번호를 저장하는 변수 초기화
while True:
    N = int(sys.stdin.readline())  # 그래프의 행의 개수 N을 입력받음
    if N == 0:  # N이 0이면 입력 종료
        break

    nodes = []  # 각 노드의 비용을 저장할 리스트
    for _ in range(N):
        # 각 행의 노드 비용을 입력받아 리스트에 추가
        nodes.append(list(map(int, sys.stdin.readline().split())))

    # 최소 비용을 저장할 2차원 리스트. costs[i][j]는 (i, j)까지의 최소 비용을 의미
    costs = [[0 for _ in range(3)] for _ in range(N)]

    # 첫 번째 행 (i=0)의 초기 비용 설정
    # costs[0][0]: 첫 번째 행의 0번째 열로 가는 경우는 존재하지 않으므로 매우 큰 값으로 초기화
    costs[0][0] = 1000001
    # costs[0][1]: 첫 번째 행의 1번째 열로 가는 비용은 해당 노드의 값과 동일
    costs[0][1] = nodes[0][1]
    # costs[0][2]: 첫 번째 행의 2번째 열로 가는 비용은 1번째 열을 거쳐야 하므로 nodes[0][1] + nodes[0][2]
    costs[0][2] = nodes[0][1] + nodes[0][2]

    # 두 번째 행부터 N-1번째 행까지 최소 비용 계산
    for i in range(1, N):
        # costs[i][0]: 현재 행의 0번째 열로 가는 최소 비용
        # 이전 행의 0번째 열 또는 1번째 열에서 현재 노드(nodes[i][0])로 이동하는 경우 중 최소값
        costs[i][0] = min(costs[i-1][0], costs[i-1][1]) + nodes[i][0]

        # costs[i][1]: 현재 행의 1번째 열로 가는 최소 비용
        # 이전 행의 0, 1, 2번째 열에서 이동하거나, 현재 행의 0번째 열에서 이동하는 경우 중 최소값
        # (costs[i][0]을 고려하는 이유는 (i,0) -> (i,1) 로 이동하는 경우가 있기 때문)
        costs[i][1] = min(costs[i-1][0], costs[i-1][1], costs[i-1][2], costs[i][0]) + nodes[i][1]

        # costs[i][2]: 현재 행의 2번째 열로 가는 최소 비용
        # 이전 행의 1, 2번째 열에서 이동하거나, 현재 행의 1번째 열에서 이동하는 경우 중 최소값
        # (costs[i][1]을 고려하는 이유는 (i,1) -> (i,2) 로 이동하는 경우가 있기 때문)
        costs[i][2] = min(costs[i-1][1], costs[i-1][2], costs[i][1]) + nodes[i][2]

    k += 1  # 테스트 케이스 번호 증가
    # 최종 목적지는 N-1번째 행의 1번째 열 (가운데 노드)이므로 costs[N-1][1] 출력
    print("{}. {}".format(k, costs[N-1][1]))

간단한 DP 문제이다.