알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 10. 그래프 이론 - 커리큘럼

  • 0
  • 0
0
0

1. 커리큘럼

  • 난이도
  • 풀이 시간
    • 50분
  • 시간 제한
    • 2초
  • 메모리 제한
    • 128MB
  • 기출
    • 핵심 유형

A. 문제

온라인 강의는 선수 강의가 있을 수 있다.
선수 강의가 있는 강의를 먼저 들어야만 해당 강의를 들을 수 있다.

총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 동시에 여러 개의 강의를 들을 수 있다고 가정한다.

듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하라.

a. 예를 들면.

N = 3
3번 강의의 선수 강의로 1번, 2번 강의가 있고, 1번과 2번 강의는 선수 강의가 없다고 가정하자.

  • 1번 강의
    • 30 시간
  • 2번 강의
    • 20 시간
  • 3번 강의
    • 40 시간

1번, 2번, 3번 강의를 수강하기까지의 최소 시간은 각각 30시간, 20시간, 70시간이다.

b. 입력 조건
  • 듣고자 하는 강의의 수 N
    • 1 <= N <= 500
  • 다음 N개 줄에 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 강의들의 번호가 자연수로 주어진다.
    • 강의 시간은 100,000 이하 자연수
  • 각 강의 번호는 1부터 N까지로 구성되며, 각 줄은 -1로 끝난다.
c. 출력 조건
  • N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력한다
d. 테스트 케이스
  • 입력 예시

    
    5
    10 -1
    10 1 -1
    4 1 -1
    4 3 1 -1
    3 3 -1
    
    
  • 출력 예시

    
    10
    20
    14
    18
    17
    
    

B. 내 답안

a. 1차 시도 (실패)

from collections import deque  
  
n = int(input())  
  
indegree = [0] * (n+1)  
time = [0] * (n+1)  
graph = [[] for _ in range(n+1)]  
  
for i in range(1, n+1):  
    array = list(map(int, input().split()))  
    time[i] = array[0]  
  
    for j in array[1:-1]:  
        graph[j].append(i)  
        indegree[i] += 1  
  
q = deque()  
result_time = time[:]  
  
for i in range(1, n+1):  
    if indegree[i] == 0:  
        q.append(i)  
print('inde', indegree)  
while q:  
    node = q.popleft()  
    print('node', node)  
    print('result', result_time)  
    print('time  ', time)  
    for i in graph[node]:  
        print('i', i)  
        result_time[i] = max(result_time[i], result_time[node]+time[i])  
  
        indegree[i] -= 1  
        print('inde', indegree)  
        if(indegree[i] == 0):  
            q.append(i)  
  
  
  
for i in result_time[1:]:  
    print(i)  
  
# 57분 / non-pass / 위상 정렬을 구현하는 방법을 잘 이해하지 못함.

b. 2차 시도 (성공)

from collections import deque  
  
n = int(input())  
  
graph = [[] for _ in range(n+1)]    # 각 노드 다음에 어떤 노드로 갈지 들어 있는 그래프  
                                    # 즉, 다음 강의 번호가 들어 있음  
time = [0] * (n+1)  # 각 강의별 강의시간  
# time = [[] for _ in range(n+1)] # 이 방법은 2차원 리스트를 만듬 / 그래서 이 문제에서는 적절하지 않음  
indegree = [0] * (n+1)  # 진입 차수 / 각 강의별 몇 개의 강의가 클리어 되었는지 확인  
  
for i in range(1, n+1):  
    array = list(map(int, input().split())) # time, (선행 강의(개수 미정)), -1 (마침)  
    time[i] = array[0]  # 강의시간은 따로 보관  
  
    for j in array[1:-1]:   # 선행 강의  
        graph[j].append(i)  # 그래프에는 선행 강의는 다음 강의가 어디인지 가리켜야함.  
                    # input은 현재 노드(i)를 수강하기 위해 선행 강의(j)가 무엇인지 주고 있음.  
        indegree[i] += 1 # 현재 노드(i)에 선행 강의 수만큼 진입 차수를 증가  
  
q = deque()  
result_time = time[:]   # 누적 강의시간 => 현재 강의를 포함하여 과거 강의시간들의 최댓값  
  
for i in range(1, n+1):  
    if indegree[i] == 0:    # 시작 강의를 선택해야함.  
        q.append(i)         # 진입 차수가 0인 것이 선행 강의가 없는 것이므로 선택.  
  
while q:  
    node = q.popleft()  
  
    for i in graph[node]:   # 여기서 node는 현재 수강하는 강의, i는 다음 강의  
        result_time[i] = max(result_time[i], result_time[node] + time[i]) # 다음 강의의 누적 강의시간은  
            # (기존 누적 강의시간)과 (현재 수강하는 강의(node)의 누적 강의시간과 다음 강의(i)의 수강시간의 합)  
            # 중 최댓값을 선정  
        indegree[i] -= 1 # 현재 강의(node)에 대한 처리가 끝났기 때문에, 다음 강의(i)의 진입 차수를 하나 빼줌  
  
        if indegree[i] == 0:    # 새롭게 진입 차수가 0인 강의를 q에 집어넣음.  
            q.append(i)  
  
print(*result_time[1:], sep='\n')

c. 회고

풀이

  • B를 실행하기 위해 A가 필요하다. 등을 봤을 때 위상 정렬이라고는 생각했다.

반성

  • 위상 정렬을 완벽하게 구현하지 못했다.

결론

  • 위상 정렬 알고리즘은 정말 여러번 반복해서 확실하게 알아야겠다.
  • 1차원 리스트는 deepcopy() 함수 대신 [:]를 사용해도 서로 다른 객체로 복사할 수 있다.

C. 문제 해설

위상 정렬 알고리즘의 응용문제다. 각 노드(강의)에 대하여 인접한 노드를 확인할 때, 인접한 노드에 대하여 현재보다 강의 시간이 더 긴 경우를 찾는다면, 더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 결과 테이블을 갱신하여 답을 구할 수 있다.

위상 정렬을 수행하면서, 매번 간선 정보를 확인하여 결과 테이블을 갱신한다.

a. 책 답안

python-for-coding-test/9.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.