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

@mildsalmon·2021-09-05 10:16

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. 테스트 케이스

입력 예시

출력 예시
```
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')