백준 10217번 문제(KCM Travel) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

10217번: KCM Travel

 

정답 코드는 아래와 같습니다.

import sys
import math
 
def solve():
  n, m, k = map(int, sys.stdin.readline().rstrip().split())
  table = [[] for _ in range(n+1)]
  for _ in range(k):
    u, v, c, d = map(int, sys.stdin.readline().rstrip().split())
    table[u].append((v, c, d))
  status = [[math.inf]*(m+1) for _ in range(n+1)]
  status[1][0] = 0
  for money in range(m+1):
    for vertex in range(1, n+1):
      if status[vertex][money] != math.inf:
        for v, c, d in table[vertex]:
          if money + c <= m:
            status[v][money+c]=min(status[v][money+c], status[vertex][money]+d)
  rst = min(status[n])
  if rst == math.inf:
    print("Poor KCM")
  else:
    print(rst)
 
t = int(input())
for _ in range(t):
  solve()
 

 

이 문제는 좋은 문제라 할 말이 많아서, 사족이 좀 있습니다.

 

<사족1>

일반적으로 코딩(수학)문제의 풀이는 다음과 같이 진행됩니다. Q: 이 문제는 어떻게 푸나요? A: 이 문제는 이렇게 생각하고 이렇게 코드를 짜면(식을 작성하면) 이렇게 풀립니다. 질문자는 다음 번에 같은 문제를 만났을 때 다시 풀 수 있을까요? 만일 푼다면 하나를 배워서 하나를 깨우친 것입니다. 아주 훌륭한 일이죠. 못 풀었다고 속상해 할 것 없습니다. 여러번 반복하면 분명 풀 수 있을 것입니다. 이번에는 조금 응용한 문제를 내보겠습니다. 과연 풀 수 있을까요? 글세요... 만일 푼다면 굉장히 똑똑한 사람이라고 생각합니다. 보통은 풀지 못할 것입니다. 여기서 문제가 발생하게 됩니다. 우리가 어떤 문제를 푸는 이유는 다음 번에 "동일한" 문제를 다시 풀 수 있기 위함이 아니라, (물론 이것도 쉬운 일은 아니지만) 다음 번에 "응용한 또는 변경한" 문제를 다시 풀 수 있기 위함이기 때문입니다. 그래서 보통은 어떻게 하나면, 비슷한 유형의 문제를 풀곤 합니다. 문제를 익히는게 아니라 유형을 익혀서 비슷한 유형은 모두 다 풀 수 있기 위함이죠. 여기서 근데 문제가 또 두 가지 발생합니다. 하나는 그 유형이 너무 많다는 것이고, 다른 하나는 새로운 유형은 어떻게 풀 수 있냐는 것입니다. 첫 번째는 근성으로 해결할 수 있습니다. 까짓거 모든 유형 다 외우면 됩니다. 열심히만 하면 된다는 것이죠. 그럼 두 번째 문제(새로운 유형)는 어떻게 해결할 수 있을까요? 단순히 열심히 해서는 잘 해결되지 않습니다. 제 경험상 다음과 같이 해결(?)됩니다. 1. 그 문제는 그냥 틀린다. 2. 머리가 좋아서 그냥 보자마자 어떻게 풀어야 할지 떠오른다. 3. 가장 쉽게 생각할수 있는 부분부터 하나씩 아이디어를 확장시켜 나가서 풀이를 완성한다. 제가 여러분에게 설명드리는 것은 3번 입니다.(물론 너무 쉬운 문제들에 대해서는 설명을 생략합니다) 가끔 이런 문구를 봅니다. "원리를 정확히 이해하면 답이(풀이가) 보인다", 이건 똑똑한 강사 본인 이야기 입니다. 보통은 원리를 이해해도 어떻게 풀어야 할지 막막한 경우가 많습니다. 저는 원리를 이해하신 분들에게 어떤 식으로 사고를 전개해나가면서 문제를 풀어낼 수 있는지를 설명하고 있습니다. 그리고 그 방식은 일관되고 몇 가지 없으므로 누구든지 익히고 사용할 수 있습니다.

 

728x90

 

이 문제도 가장 쉽게 생각이 드는 부분부터 하나씩 확장시켜 나가보도록 하겠습니다.

첫 번째로 이 문제는 최단거리를 구하는 문제라는 것을 알 수 있습니다.

그러면 그 다음으로 떠올라야 하는 것은 Edge에 음수가 있는지를 살피는 것입니다.

즉, Dijkstra 알고리즘을 사용할 수 있는지 보는 것이죠.

Weight 로 사용될 값(돈, 시간)에 음수가 없으니 Dijkstra 를 적용하면 될 것 같다는 생각이 먼저 떠오를 것입니다.

그래서 graph 를 구성하려고 생각을 해보니, weight 이 그래서 돈이 되어야 할지 시간이 되어야 할지 모르겠습니다.

모를 때에는 시각화를 통해서(그림을 그려서) 구체적으로 내가 무엇을 모르는지 이해하면 좋습니다.

그림을 그려보니, 무엇이 문제인지 명확합니다.

Dijkstra 알고리즘은 그리디 알고리즘이므로, 어떤 edge 를 선택할지를 그 순간에 결정할 수 있어야 합니다.

그런데 어떤 것이 먼저 선택되어야 할지 그 순간에 알 수가 없는 것이 문제입니다.

이것은 결국 Dijkstra 알고리즘을 사용할 수 없음을 의미합니다.

 

<사족2>

실제 세상에는 풀리지 않는 또는 풀릴지 안 풀릴지 아직 모르는 문제가 존재합니다.(NP-complete 등) 하지만 대회, 코테, 시험 등에 출제된 문제는 해답(풀이)이 반드시 존재합니다. 따라서 내가 어떤 문제의 풀이를 떠올리고 적용하려는데 적용할 수 없다면, 다른 방식이 있다는 것을 의미합니다. 다른 방식이 무엇인지 찾는 가장 좋은 방법은 문제에서 "아직 사용하지 않은 조건을 찾고 그것을 사용하는 것"입니다. 문제 출제자들은 불필요한 조건을 추가로 두지 않는 경향이 있습니다.(왜 그런지에 대한 설명까지 하기엔 너무 길어져서 생략하겠습니다) 다시 말해서 어떤 문제를 풀기 위해서는 주어진 조건을 모조리 사용해야만 하는 경우가 많다는 것입니다. 따라서 문제가 잘 풀리지 않는 경우에는 아직 사용하지 않은 조건이 있는지 확인하고 그 조건을 사용하려고 노력하다보면 풀리는 경우가 있습니다.

 

문제로 다시 돌아가보겠습니다. 어떤 조건을 사용하지 않은 것인지 살펴보니, 비용에 제약이 있다는 내용이 있는데,

Dijkstra 로 생각했을 때에는 이 조건이 사용되지 않았습니다.

자 그럼 여기서는 이 조건을 어떻게 사용할 수 있을지 생각을 해보는 것입니다.

지금까지 공부했던 내용을 돌아보고 어떤 것을 적용할 수 있을지 생각해보면, 지금 이 상황이 평범한 배낭 문제(백준 12865번)와 비슷하다는 것을 눈치챌 수 있습니다.

이 문제의 가장 어려운 지점이 바로 이것을 생각해내는 것입니다.

여기까지 생각했다면 그 다음부터는 간단해집니다. DP를 풀면 되는 것이죠.

 

<사족3>

학창시절 수학책을 보면 이론을 설명하고 그 뒤에 예제가 있기 마련입니다. DP에 대하여 공부하였다면, 필수 예제는 피보나치 수열(백준 2748번), 평범한 배낭(백준 12865번), RGB거리(백준 1149번), 계단 오르기(백준 2579번) 라고 할 수 있습니다. 아직 이 문제들을 풀지 않았다면 반드시 풀기를 권합니다. 예제를 풀어야 하는 이유는 두 가지 인데, 하나는 이론을 정확하게 이해하기 위함이고, 다른 하나는 이 문제에서 평범한 배낭 문제와 유사한 상황임을 떠올린 것 처럼, 예제의 상황들을 기억하면서 비슷한 상황이 발생하였을 때 예제와 같은 방식으로 풀어내기 위함입니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=B4Ivp_ebm4c 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)