[python] 백준 23258 밤편지

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

23258번: 밤편지

 

문제 해결

• DP의 전형적인 문제이다.
• 우선 $\sum_{i=1}^{i=C-1} 2^{i} < 2^{C}$ 을 알아야한다. 따라서 C이하의 마을들만 지나면 문제가 없다.
• DP[k][i][j]를 k이하의 집들만 지나면서 i에서 j까지 가는 최소 시간을 의미한다.
• 초기 주어진 정보를 DP[0][i][j] 에 저장한다.
• 참고로 i,j>k일 때에 DP[k][i][j]이면 지날 수 없다. 하지만 지날 수 없는 만큼 출력할 일이 없으므로 k-1에서 정보 DP[k-1][i][j]에서 그대로 가져올 수 있다. (즉 출력할 일이 없기 때문에 정보를 저장해놔도 된다. DP[k][i][j]는 안되도 DP[k+1][i][j]는 가능할 수 있기 때문에 그대로 옮겨서 쓸 수 있다.)
• 따라서 DP[k][i][j] = min(DP[k-1][i][j], DP[k-1][i][k] + DP[k-1][k][j])로 최소 시간을 계산한다.
• 주의할 점이 있는데 DP = [[[0]*(N+1)]*(N+1)]for _ in range(N+1)]이렇게 쓰면 안된다는 것을 알았다.
  • DP = [[[0]*(N+1)]*(N+1)]for _ in range(N+1)] 은 DP = [[[0]*(N+1) for _ in range(N+1)]for _ in range(N+1)]과 초기화가 다르다.
  • 외부 리스트는 N+1번 반복되며, 각각의 내부 리스트는 N+1번 반복되지만, 모든 내부 리스트가 동일한 참조를 가지고 있습니다. 즉, 모든 내부 리스트가 동일한 객체이므로, D[i][j]의 값을 변경하면 D[i'][j'] (단, i=i', j=j')의 값도 동일하게 변경됩니다.

N = 2
D1 = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
D2 = [[[0]*(N+1)]*(N+1) for _ in range(N+1)]

# D1의 경우
D1[0][0][0] = 1
print(D1)  # 출력: [[[1, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 0], [0, 0, 0]]]

# D2의 경우
D2[0][0][0] = 1
print(D2)  # 출력: [[[1, 0, 0], [1, 0, 0], [1, 0, 0]], [[1, 0, 0], [1, 0, 0], [1, 0, 0]], [[1, 0, 0], [1, 0, 0], [1, 0, 0]]]

 

CODE

import sys
input = sys.stdin.readline
INF = sys.maxsize

def solve():
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                D[k][i][j] = min(D[k - 1][i][j], D[k - 1][i][k] + D[k - 1][k][j])


def result(C,s,e):
    if D[C-1][s][e] == INF:
        print(-1)
    else:
        print(D[C-1][s][e])

if __name__ == "__main__":
    N, Q = map(int, input().split())
    D = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)] 
    for i in range(1,N+1):
        for j, num in enumerate(list(map(int, input().split())),1):
            if i != j and num == 0:
                D[0][i][j] = INF
                continue
            D[0][i][j] = num
    solve()

    for _ in range(Q):
        C, s, e = map(int, input().split())
        result(C,s,e)