[백준] 4883번 삼각 그래프 ★

💡문제접근

• 가장 위의 중간 정점에서 가장 아래의 중간 정점으로 이동하는 최단 경로를 구하는 문제로 그래프의 방향성을 잘 생각해 코드로 구현하면 해결할 수 있는 비교적 간단한 문제였는데 머릿속으로 경우를 따지는 과정에서 하나를 놓쳐 생각보다 오래 걸렸던 문제였다.

💡코드(메모리 : 72620KB, 시간 : 444ms)

import sys
input = sys.stdin.readline

k = 1
while True:
    N = int(input())
    if N == 0:
        break
    graph = [list(map(int, input().strip().split())) for _ in range(N)]
    dp = [[0] * 3 for _ in range(N)]
    dp[0][1] = graph[0][1]				# 중간
    dp[0][2] = dp[0][1] + graph[0][2]	# 오른쪽
    dp[1][0] = dp[0][1] + graph[1][0]   # 왼쪽
    dp[1][1] = graph[1][1] + min(dp[0][1], dp[1][0], dp[0][2])	# 중간
    dp[1][2] = graph[1][2] + min(dp[0][2], dp[1][1], dp[0][1])	# 오른쪽

    for i in range(2, N):
        for j in range(3):
            if j == 0:      # 왼쪽 라인
                dp[i][j] = graph[i][j] + min(dp[i-1][j], dp[i-1][j+1])
            elif j == 1:    # 중간 라인
                dp[i][j] = graph[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1], dp[i][j-1])
            else:			# 오른쪽 라인
                dp[i][j] = graph[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
    print(str(k) + ".", dp[-1][1])
    k += 1

💡소요시간 : 35m