[그래프] 그래프 알고리즘 (6) 실전 문제 - 커리큘럼

이코테 p.303 실전 문제 - 커리 큘럼

입력 예시

5 10 -1 10 1 -1 4 1 -1 4 3 1 -1 3 3 -1

출력 예시

10 20 14 18 17

내 소스코드

• cost_array 리스트
  • cost_array[i]는 i번 강의를 듣는 데 걸리는 시간
• graph 리스트
  • graph[1] = [0, 2, 3, 4]라면 1번 노드는 2, 3, 4번 노드와 연결되어 있음을 의미
  • 0번 인덱스의 요소는 건너뜀
• 위상 정렬 알고리즘 사용
  • indegree가 0이 될 때 q에 삽입 & result 값 갱신
  • result[다음 노드] = max(result[다음 노드], result[현재 노드] + cost_array[다음 노드])
• 주의할 점)
  • 아래 소스코드의 result = cost_array처럼 단순히 대입 연산으로 리스트를 복사하면 값이 변경되는 문제가 발생할 수 있음
  • copy 라이브러리의 deepcopy() 함수 사용하기

from collections import deque

# n 입력 받기
n = int(input())

graph = [[] for _ in range(n + 1)]
cost_array = [0] * (n + 1) # 강의 시간을 저장하기 위한 리스트

for i in range(1, n + 1):
  input_data = list(map(int, input().split()))
  cost_array[i] = input_data[0] # 강의 시간 저장
  for j in range(1, len(input_data) - 1):
    graph[input_data[j]].append(i) # 간선 정보를 그래프에 기록

indegree = [0] * (n + 1)
# 진입 차수 기록
for i in range(1, n + 1):
  for j in graph[i]:
    indegree[j] += 1

# 강의를 수강하는데 걸리는 시간을 저장하는 최종 리스트
result = cost_array
# 위상 정렬 알고리즘
def topology_sort():
  q = deque()
  for i in range(1, n + 1):
    if indegree[i] == 0: # 진입 차수가 0인 경우
      q.append(i) # 큐에 삽입
  # 큐가 빌 때까지
  while q:
    now = q.popleft()
    for i in graph[now]:
      indegree[i] -= 1
      if indegree[i] == 0: # 진입차수가 0이 될 경우
        result[i] = max(result[i], result[now] + cost_array[i]) # result 값 갱신
        q.append(i)

topology_sort()

for i in range(1, n + 1):
  print(result[i])

교재 소스코드

• 각 노드(강의)에 대하여 인접한 노드를 확인할 때, 인접한 노드에 대하여 현재보다 강의 시간이 더 긴 경우를 찾는다면, 더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 결과 테이블 갱신
  • result[i] = max(result[i], result[now] + time[i]) 이 부분
• 위상 정렬을 수행하면서 매번 간선 정보를 확인하여 결과 테이블 갱신
• result 리스트
  • 결과 테이블
  • 최종적으로 각 강의를 수강하기까지의 최소 시간
• time 리스트
  • 각 강의 시간
• time 리스트 변수의 값을 복사하여 result 리스트 변수의 값으로 설정하기 위해 copy.deepcopy() 함수 사용
  • 그냥 대입 연산으로 구현할 경우 문제가 발생할 수 있음

from collections import deque
import copy

# 노드의 개수 입력받기
v = int(input())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결리스트(그래프) 초기화
graph = [[] for _ in range(v + 1)]
# 각 강의 시간을 0으로 초기화
time = [0] * (v + 1)

# 방향 그래프의 모든 간선 정보를 입력받기
for i in range(1, v + 1):
  data = list(map(int, input().split()))
  time[i] = data[0] # 첫 번째 수는 시간 정보를 담고 있음
  for x in data[1:-1]:
    indegree[i] += 1
    graph[x].append(i)

# 위상 정렬 함수
def topology_sort():
  result = copy.deepcopy(time) # 알고리즘 수행 결과를 담을 리스트
  q = deque() # 큐 기능을 위한 deque 라이브러리 사용

  # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
  for i in range(1, v + 1):
    if indegree[i] == 0:
      q.append(i)

  # 큐가 빌 때까지 반복
  while q:
    # 큐에서 원소 꺼내기
    now = q.popleft()
    for i in graph[now]:
      result[i] = max(result[i], result[now] + time[i])
      indegree[i] -= 1
      # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
      if indegree[i] == 0:
        q.append(i)

  # 위상 정렬을 수행한 결과 출력
  for i in range(1, v + 1):
    print(result[i])

topology_sort()