새소식

반응형
Algotithms

[이것이 코딩테스트다] 커리큘럼

  • -
728x90
반응형

문제

  • 선수 강의가 있는 경우, 선수 강의를 먼저 들어야 해당 강의를 들을 수 있다.
  • 모든 강의는 1번부터 N번까지의 번호를 가진다.
    • 1 <= N <= 500
  • 동시에 여러 개의 강의를 들을 수 있다.
  • N개의 강의를 들을 때 수강하기까지 걸리는 최소 시간은?

 

풀이

  • 전형적인 위상정렬 문제
  • 시간 복잡도 : O( V + E ) 이므로 가능하다
  • 각 강의에 대해 수강하기까지 걸리는 최소 시간을 각각 구해야 하고, 이는 선수 과목의 최대 시간이 된다.
    • 각 강의에 대해 선수과목+현재 강의 시간현재 강의 수강하는데 필요한 시간 중 더 큰 값을 넣는다.

 

from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)]
time = [0] * (N+1)
indegree = [0] * (N+1)      # 진입 차수

for i in range(1, N+1):
    data = list(map(int, input().split()))
    time[i] = data[0]
    for pre in data[1:-1]:    # 각 선수과목에 대해
        indegree[i] += 1        # 진입차수 +1
        graph[pre].append(i)    # 그래프 연결

result = time[:]        # 결과 담을 리스트
q = deque()

# 진입 차수가 0인 노드 삽입
for i in range(1, N+1):
    if indegree[i] == 0 :
        q.append(i)

# 큐가 빌 때까지 반복
while q:
    now = q.popleft()

    for i in graph[now]:
        # 현재 강의 수강하는데 필요한 시간 VS 선수과목 + 현재 강의 시간
        result[i] = max(result[i], result[now]+time[i])
        indegree[i] -= 1

        if indegree[i] == 0:
            q.append(i)

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

 

References

  • 이것이 코딩테스트다 ch10 그래프 이론 - 커리큘럼
반응형

'Algotithms' 카테고리의 다른 글

[백준] 16434 드래곤 앤 던전  (0) 2023.04.21
[백준] 17390 이건 꼭 풀어야 해!  (0) 2023.04.21
코테 References  (0) 2023.04.21
[백준] 1647 도시분할 계획  (0) 2023.04.20
[이것이 코딩테스트다] 팀 결성  (0) 2023.04.20
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.