1005번 문제풀이

 

백준 1005번 문제

* 문제 풀이에 필요한 개념

recursive function ( DFS ), list-comprehension, memoization 

 

1005번 문제는 재귀함수를 이용해서 풀 수 있다.

즉 역으로 추적하는 것인데, 큰 컨셉은 다음과 같다.

 

4번을 마치는데 필요한 시간 = max(2번을 마치는데 필요한 시간, 3을 마치는데 필요한 시간) + 4번에 걸리는 시간

3번을 마치는데 필요한 시간  = max(1을 마치는데 필요한 시간) + 3번에 걸리는 시간

 

일반화해보면,

n번 node를 마치는데 필요한 시간 = max([선행node를 마치는데 필요한 시간]) + n번 노드에 걸리는 시간

 

이러한 풀이방식을 DFS (Depth-First-Serch) , 깊이우선탐색이라고 부른다.

4번노드 -> 2번노드 -> 1번노드 , -> 3번노드 -> 1번노드. 이런 식으로 하위노드에 걸리는 시간을 하나씩 탐색하며 값을 구하는 것이다.

 

 

풀이과정은 다음과 같다.

이를 구현한 코드는 다음과 같다.

import sys
sys.setrecursionlimit(10**6) # 파이썬 최대 재귀깊이 높이기

# ways_dict : 완료하기위해 해야하는 선행노드 dict
# cost_dict : 시간을 단축하기 위한 node별 cost 저장 dict
def checkCost(node:int) -> int:
  if (node not in ways_dict.keys()): # 최하위 노드
    return cost_list[node - 1]
  if (node in cost_dict.keys()):
    return cost_dict[node]
  
  result = max([checkCost(before_node) for before_node in ways_dict[node]]) + cost_list[node - 1]
  cost_dict[node] = result
  return result

N = int(sys.stdin.readline())
  
for _ in range(N):
  # 입력값 받기
  node_cnt, way_cnt = map(int, sys.stdin.readline().split())
  cost_list = list(map(int , sys.stdin.readline().split()))
  
  ways_dict = {} # 완료까지 필요한 선행노드경로 넣기
  cost_dict = {} # 노드마다 필요한 cost 저장해놓기
  
  for _ in range(way_cnt):
    start_node, end_node = map(int, sys.stdin.readline().split())
    if (end_node in ways_dict.keys()): ways_dict[end_node].append(start_node)
    else: ways_dict[end_node] = [start_node]
  
  final_node = int(input())
  
  # 문제풀이
  print(checkCost(final_node))