# [이.취.코] Chap 10. 그래프 이론 - 커리큘럼 - Author: @mildsalmon - Published: 2021-09-05 - Updated: 2021-09-08 - Source: http://blex.me/@mildsalmon/chap-10-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0-%EC%BB%A4%EB%A6%AC%ED%81%98%EB%9F%BC - Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 그래프, 위상정렬, 커리큘럼 --- # 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차 시도 (실패) ```python 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차 시도 (성공) ```python 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)](https://github.com/ndb796/python-for-coding-test/blob/master/10/9.py) # 참고문헌 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년