[python] 백준 - 4883. 삼각 그래프

🤔문제 해결

S1 | 다이나믹프로그래밍

 

최소가중치? 라고 생각해서 별 생각없이 다익스트라로 풀었더니 바로 시간초과

다시 읽어보니 경로가 각 지점마다 단순해서 다이나믹프로그래밍으로 푸는 문제였다.

 

문제에서 주어진 삼각그래프와 똑같은 크기의 2차원리스트를 만든다.

리스트의 각 요소는 i,j에 도달 할 때의 가장 최솟값을 저장한다.

 

이제 dp 값을 저장하는 방법을 설명하면 먼저 1행까지는 직접 값을 채워 넣고, 나머지는 for문을 돌린다.

• (1,0): (0,1)에서 오는 값
• (1,1): (0,1), (1,0)에서 오는 값
• (1,2): (0,1), (1,1),  (0,1)+(0,2)  에서 오는 값

여기서 중요한건 노란색으로 표시한 저 부분이다.

문제에서 각 노드의 가중치는 정수이다. 다시 말해서 음수가 포함되어 있다는 뜻.(저 부분 때문에 한참 해맸다)

7 -> 6 이 7 -> 5 -> 6 보다 당연히 작다

하지만 5가 만약 -5라면

6 -> -6 보다 7 -> -5 -> 6이 더 작다. 그러므로 이렇게 돌아서 가는 경로도 계산해줘야 한다.

 

💨  tip! 문제에서 노드의 값이 정수라는 점

 

💻소스 코드

import sys


def solution(n, graph):
    dp = [[0] * 3 for _ in range(n)]

    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])

    for i in range(2, n):
        for j in range(3):
            if j == 0:
                min_value = min(dp[i - 1][j], dp[i - 1][j + 1])
            elif j == 1:
                min_value = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1], dp[i][j - 1])
            else:
                min_value = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])

            dp[i][j] = min_value + graph[i][j]

    print(f'{tc}. {dp[-1][1]}')


if __name__ == "__main__":

    tc = 0
    while True:
        a = int(input())
        if a == 0:
            break
        b = [list(map(int, sys.stdin.readline().split())) for _ in range(a)]
        tc += 1
        solution(a, b)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

4883번: 삼각 그래프

---

문제

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

삼각 그래프는 사이클이 없는 그래프로 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은 최소 비용이다.