[Gold V] 선수과목 (Prerequisite) - 14567
성능 요약
메모리: 142820 KB, 시간: 376 ms
분류
방향 비순환 그래프, 다이나믹 프로그래밍, 그래프 이론, 위상 정렬
제출 일자
2024년 11월 28일 21:10:35
문제 설명
올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.
- 한 학기에 들을 수 있는 과목 수에는 제한이 없다.
- 모든 과목은 매 학기 항상 개설된다.
모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성하여라.
입력
첫 번째 줄에 과목의 수 N(1 ≤ N ≤ 1000)과 선수 조건의 수 M(0 ≤ M ≤ 500000)이 주어진다. 선수과목 조건은 M개의 줄에 걸쳐 한 줄에 정수 A B 형태로 주어진다. A번 과목이 B번 과목의 선수과목이다. A < B인 입력만 주어진다. (1 ≤ A < B ≤ N)
출력
1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지를 한 줄에 공백으로 구분하여 출력한다.
풀이
# N : 과목의 수, M : 선수 조건의 수
N, M = map(int, input().split())
# 선수 조건 그래프 및 진입 차수 배열 초기화
graph = [[] for _ in range(N + 1)]
in_degree = [0] * (N + 1)
# 선수 조건 입력 처리
for _ in range(M) :
A, B = map(int, input().split())
graph[A].append(B)
in_degree[B] += 1
# 위상 정렬 수행
q = []
res = [0] * (N + 1)
# 진입 차수가 0인 노드부터 시작
for i in range(1, N + 1) :
if in_degree[i] == 0 :
q.append(i)
res[i] = 1 # 첫 학기부터 수강 가능
while q :
curr = q.pop(0)
for neighbor in graph[curr] :
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0 :
q.append(neighbor)
res[neighbor] = res[curr] + 1
print(*res[1:])
이 코드는 문제에서 주어진 선수과목 조건을 바탕으로, 각 과목을 최소 몇 학기에 이수할 수 있는지를 계산하는 프로그램입니다. 아래에 코드의 동작을 단계별로 설명하겠습니다.
1. 함수 정의
def calculate_min_semesters(N, M, prerequisites):
- N: 과목의 수 (1번부터 NN번 과목까지).
- M: 선수 조건의 수 (선수과목 관계의 개수).
- prerequisites: 선수과목 조건을 나타내는 리스트, 각 요소는 (A, B) 형태로 A 과목을 수강해야 B 과목을 수강할 수 있음을 나타냄.
2. 그래프와 진입 차수 초기화
graph = [[] for _ in range(N + 1)]
in_degree = [0] * (N + 1)
- graph:
- 각 과목에 대해 선수과목 관계를 저장하는 인접 리스트입니다.
- graph[A]는 A 과목을 선수과목으로 요구하는 과목들의 리스트입니다.
- in_degree:
- 각 과목의 진입 차수를 저장하는 배열입니다.
- 진입 차수는 해당 과목을 수강하기 위해 선수과목으로 지정된 과목의 개수입니다.
3. 선수과목 관계 입력
for A, B in prerequisites:
graph[A].append(B)
in_degree[B] += 1
- A → B 관계를 그래프에 추가합니다.
- graph[A]에 B를 추가하여 A가 B의 선수과목임을 저장합니다.
- B의 진입 차수(in_degree[B])를 1 증가시킵니다.
예를 들어, 입력 prerequisites = [(1, 2), (2, 3)]가 주어지면:
- graph = [[], [2], [3], [], ..., []]
- in_degree = [0, 0, 1, 1, 0, ..., 0]
4. 초기 큐와 학기 저장 배열 초기화
q = []
semesters = [0] * (N + 1)- queue:
- 현재 진입 차수가 0인 과목들을 저장하는 큐입니다.
- 이 큐를 이용해 위상 정렬을 수행합니다.
- semesters:
- 각 과목을 최소 몇 학기에 이수할 수 있는지를 저장하는 배열입니다.
- semesters[i]는 ii번 과목을 이수할 수 있는 최소 학기를 의미합니다.
5. 진입 차수가 0인 노드 큐에 삽입
for i in range(1, N + 1):
if in_degree[i] == 0:
queue.append(i)
semesters[i] = 1 # 첫 학기에 들을 수 있음
- 진입 차수가 0인 과목들은 선수과목 없이 들을 수 있으므로, 첫 학기부터 수강 가능합니다.
- semesters[i] = 1로 설정하여 첫 학기를 기록합니다.
6. 위상 정렬 수행
while queue:
current = q.pop(0)
for next_course in graph[current]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
semesters[next_course] = semesters[current] + 1- 큐에서 과목 꺼내기:
- 큐의 가장 앞에 있는 과목(current)을 꺼내고, 이 과목을 선수과목으로 요구하는 과목들에 대해 처리합니다.
- 진입 차수 갱신:
- current 과목이 선수과목으로 설정된 모든 과목(next_course)에 대해 진입 차수를 1 감소시킵니다.
- 다음 학기 과목 추가:
- 만약 next_course의 진입 차수가 0이 되었다면, 선수과목 조건을 모두 만족했으므로 큐에 추가하고, semesters[next_course]를 갱신합니다.
- semesters[next_course] = semesters[current] + 1로 설정하여, current를 이수한 다음 학기에 이수 가능하다고 기록합니다.
7. 결과 반환
return semesters[1:] # 1번 과목부터 N번 과목까지
- 1번 과목부터 NN번 과목까지 최소 학기를 리스트로 반환합니다.
8. 입력 및 출력 처리
N, M = map(int, input().split())
prerequisites = [tuple(map(int, input().split())) for _ in range(M)]
res = calculate_min_semesters(N, M, prerequisites)
print(*res)- N, M 및 선수 조건을 입력받아 prerequisites 리스트로 저장합니다.
- calculate_min_semesters 함수를 호출하여 결과를 계산합니다.
- 결과 리스트를 공백으로 구분하여 출력합니다.
동작 예시
입력
3 2
2 3
1 2
동작
- 그래프와 진입 차수 초기화:
- graph = [[], [2], [3], []]
- in_degree = [0, 0, 1, 1]
- 초기 큐 설정:
- 진입 차수가 0인 노드: [1]
- queue = deque([1]), semesters = [0, 1, 0, 0]
- 위상 정렬:
- 1번 꺼냄: queue = [], 2번 추가 (semesters[2] = 2).
- 2번 꺼냄: queue = [], 3번 추가 (semesters[3] = 3).
- 결과:
- semesters = [0, 1, 2, 3]
- 출력: 1 2 3
시간 복잡도
- 그래프 생성: O(M) (간선 수만큼 반복).
- 위상 정렬: O(N+M) (노드 및 간선 수만큼 반복).
- 전체: O(N+M).
공간 복잡도
- 그래프: O(N+M).
- 진입 차수 배열 및 기타 데이터 구조: O(N).
- 전체: O(N+M).
이 코드는 문제에서 요구한 조건을 충족하며, 효율적으로 작동합니다.