[BOJ] Q2157 여행

[BOJ] Q2157 여행

Question

Language: Python

Difficulty: Gold 4

전형적인 DP 문제로, Node 에 대해 M개 이하를 거쳐 목적지 노드로 가는 과정을 구하는 문제이다.

해당 문제에서 dp를 node,M 2개의 변수에 대해서 설정하면 된다.

dp=[[-1] * (M+1) for _ in range(N+1)]

출발지인 dp[1][1] 부터 시작한다.

dp[i][j] 가 존재하면서, graph[i][k]을 통해 i->k로 가는 길이 있으면 dp[k][j+1]의 값을 갱신하는 구조이다.

if graph[i][k]:
    dp[k][j+1]=max(dp[k][j+1],dp[i][j]+graph[i][k])

Solution

def solution():
    dp=[[-1] * (M+1) for _ in range(N+1)]
    dp[1][1]=0
    
    for i in range(1,N+1):
        for j in range(1,M):
            if dp[i][j] == -1:
                continue
            for k in range(i+1,N+1):
                if graph[i][k]:
                    dp[k][j+1]=max(dp[k][j+1],dp[i][j]+graph[i][k])
                    
    return max(dp[N])
if __name__ == "__main__":
    N,M,K=map(int,input().split())
    graph=[[0] * (N+1) for _ in range(N+1)]
    for _ in range(K):
        v1,v2,cost=map(int,input().split())
        graph[v1][v2]=max(graph[v1][v2],cost)
    print(solution())