[백준]_14220번 : 양아치 집배원(파이썬)

14220번: 양아치 집배원

 

애초에 문제 자체가 이해하기 되게 어려웠던 문제이다. 예제 입력들을 이용해서 현 상황을 이해해 보자.

 

예제 입력 1

 

1행 2열에 있는 1이 의미하는 것은 1번 도시에서 2번 도시로 이동하는데 걸리는 비용이다. 그래서 만일 1행 2열의 1을 선택하면 이 시점까지의 이동 비용은 1이고 총 방문한 도시의 수는 2(1번 도시에서 출발, 2번 도시에 결국 도착. 총 2개의 도시를 방문)이다.

 

 

대각 성분들이 전부 0인 이유는 예를 들어 n번 도시에서 n번 도시로 이동할 이유조차 없고 비용 또한 존재하지 않는다. 

 

이 예시의 정답이 2 임을 알고 있으니까 한 번 어떤 도시들을 경유하면 될지 추론해 보자. n=3이므로 2개의 비용만 고르면 2+1 개의 도시를 방문한 것이기 때문에 2개의 비용만 고르면 된다.

 

1번 도시 -(1)-> 2번 도시 -(1)-> 3번 도시 : 총비용 = 2

또는

3번 도시 -(1)-> 2번 도시 -(1)-> 3번 도시 : 총 비용 = 2

또는

2번 도시 -(1)-> 3번 도시 -(1)-> 2번 도시 : 총 비용 = 2

 

이처럼 다양한 경우가 있지만 우리는 최소 비용만 고르면 되기 때문에 답은 2가 됨을 알 수 있다. 방향 그래프로 이해하면 편하다.

n개의 도시를 방문하려면 왜 비용을 n-1개만 선택해도 되는지 직관적으로 이해가 가능하다.

 

예제 입력 2

방향 그래프를 그려보자.

 

어느 도시에서 출발해도 3개의 도시를 전부 방문할 수 없기 때문에 -1을 출력해야 한다.

 

전략

 

이제 문제의 개요를 이해했으니 풀이 방법만 떠올리면 된다. 만약 n=4이라고 가정하자. 우리한테 이미 n=3일 때의 최소 비용 테이블이 존재한다면...

 

n=3일 때 1번 도시에서 출발하면 4, 2번 도시에서 출발하면 5, 3번 도시에서 출발하면 8, 4번 도시에서 출발하면 10, 와 같은 정보를 미리 알고 있다고 가정하자. 이 정보를 배열에 담아 표현하면 [4, 5, 8, 10](A 배열)와 같다.

 

이제 위의 정보만 갖고 테이블을 n=4인 상황으로 업데이트하면 된다. 예를 들어 1번 도시에서 다른 도시로의 이동에 대한 비용이 각각 [0, 2, 1, 4](init 배열)라고 가정하자. 이 비용 배열을 활용해서 우리는 A의 첫 번째 원소를 업데이트할 수 있다.

 

n=3일 때의 비용 정보를 알고 있을 때, 

1번 도시에서 출발하고 2번 도시로 가는 경우의 비용 = 2+5 = 7

1번 도시에서 출발하고 3번 도시로 가는 경우의 비용 = 1+8 = 9

1번 도시에서 출발하고 4번 도시로 가는 경우의 비용 = 4+10 = 14   

-> 7, 9, 14중에서 최솟값은 7이므로 1번 도시에서 출발하여 총 4개의 도시를 방문할 때의 비용 최솟값은 7 임을 알 수 있고 이 값을 새로운 A'배열의 가장 첫 번째 인덱스에 업데이트해주면 된다. 

 

나머지 도시에 대한 init 배열이 있을 것이기 때문에 위와 같은 과정을 동일하게 거쳐 A'배열을 만들 수 있다. 

A' = [7, 6, 12, 11](가정일 뿐이다) 즉 2번 도시에서 출발했을 때의 비용이 최소임을 알 수 있다.

 

하지만 애초에 n=3일 때의 배열을 구하려면 n=2일 때의 배열이 필요하고 또 이를 구하려면 n=1일 때의 배열이 필요하다. 이런 식으로 차근차근 기록해줘서 기록된 결과를 사용해주는 메모이제이션 기법을 활용하는 동적 계획법을 바텀 업으로 사용하면 된다.

 

import sys

input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n)] # 방향 그래프의 간선 저장.
for start in range(n):
    for finish, cost in enumerate(map(int, input().split())):
        if cost != 0: # 이동 불가능한 간선 제외
            graph[start].append((finish, cost))

dp = [[0] * n for _ in range(n)]

for dp_idx in range(1, n):
    for start in range(n):
        if graph[start]:
            dp[dp_idx][start] = min(dp[dp_idx - 1][finish] + c for finish, c in graph[start])

ans = min(dp[n - 1])
print(ans)

 

하지만 아직 예외를 처리해주지 못한다. 

 

앞서 이동 불가능한 간선들을 제외해서 graph에 넣어 주었음을 알 수 있다. 그리고 이후에 graph[start]에 원소가 존재해야지만 dp[dp_idx]를 업데이트해주었음을 알 수 있다. 

 

즉 초기값에 충분히 큰 수(10**10)를 집어넣고 dp연산을 해주면 -1을 출력해야 하는 상황에서는 특정 시작 지점(-1을 유발하는 도시)에서는 dp 업데이트가 끝까지 수행되지 않을 것이다(초기 값인 10**10이 업데이트되지 않은 채 남아 있음). 결국 min(dp[n-1])의 값이 10**10이면 도시를 n번 방문할 수 없는 상황인 것이다. 조금이라도 다른 도시를 방문하고 더 이상 갈 길이 막힌 경로의 최종 비용은 반드시 10**10보다 클 것이다. 왜냐하면 이동하는 동안 쌓인 비용(c)과 이후에 막다른 길에 다다랐을 때 10**10을 덧셈으로 받을 것이기 때문에 최종 비용은 10**10+c일 것이다.

 

최종 코드>>

import sys

input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n)]
for start in range(n):
    for finish, cost in enumerate(map(int, input().split())):
        if cost != 0:

dp = [[10 ** 10] * n for _ in range(n)]
dp[0] = [0] * n

for dp_idx in range(1, n):
    for start in range(n):
        if graph[start]:
            dp[dp_idx][start] = min(dp[dp_idx - 1][finish] + c for finish, c in graph[start])

ans = min(dp[n - 1])
print(ans if ans != 10 ** 10 else -1)