[백준 14567] 선수과목 (Prerequisite) (Python)

문제

올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.

1. 한 학기에 들을 수 있는 과목 수에는 제한이 없다.
2. 모든 과목은 매 학기 항상 개설된다.

모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성하여라.

 

입력

첫 번째 줄에 과목의 수 N(1 ≤ N ≤ 1000)과 선수 조건의 수 M(0 ≤ M ≤ 500000)이 주어진다. 선수과목 조건은 M개의 줄에 걸쳐 한 줄에 정수 A B 형태로 주어진다. A번 과목이 B번 과목의 선수과목이다. A < B인 입력만 주어진다. (1 ≤ A < B ≤ N)

 

출력

1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지를 한 줄에 공백으로 구분하여 출력한다.

 

예제

 

문제를 보고 일단, 선수 조건, 선수 과목이 필요하지 않은 과목, 수강완료 과목 이 tp 가지 list를 만들면 된다

고 생각하였다.

 

<알고리즘>

1. 선수조건 리스트(pre) for문

2. 수강완료 리스트(complited)에 선수조건이 모두 들어있는 경우, 해당 과목 수강 가능

3. 모든 과목이 수강완료가 될때까지 반복

첫 코드

n, m = map(int, input().split())

complited = [(i+1) for i in range(n)]
pre = [[] for _ in range(n + 1)]
result= [1 for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    pre[b].append(a)
    if b in complited : complited.remove(b)
    result[b] = 0

def solution(pre, complited):
    term = 1
    temp = complited.copy()
    while len(complited) < n:
        term += 1
        complited = temp.copy()
        for i in range(1, n+1):
            a = set(pre[i])
            b = set(complited)
            if pre[i] and a.issubset(b):
                result[i] = term
                temp.append(i)
                pre[i] = []
    for i in range(1, n+1):
        print(result[i], end = ' ')        

solution(pre, complited)

 

위와 같이 코드를 작성하였지만 시간 초과가 발생했다.

그래서 BFS 알고리즘을 이용하여 코드를 다시 작성하였다.

 

<알고리즘>

1. queue에 선수 조건이 필요없는 과목들을 (과목번호, 1) 형식으로 넣어준다

2. queue에서 나온 값이 선수과목인 과목을 queue에 다시 넣고 수강완료과목 리스트 complited에 수강 가능 학기 번호를 (선수과목 수강 가능 학기 + 1) 로 업데이트 해준다

3. queue에 요소가 없을때까지 반복

from collections import deque

n, m = map(int, input().split())

complited = [1 for i in range(n+1)]
# 선수조건 리스트
pre = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    # 선수 조건 리스트
    pre[a].append(b)
    # 수강 완료 과목 리스트
    complited[b] = 0

def bfs(pre, complited):
    queue = deque()
    for i in range(1, n + 1):
        if complited[i] == 1 : queue.append((i, 1))
    while queue:
        s, t = queue.popleft()
        for i in pre[s]:
            queue.append((i, t + 1))
            complited[i] = t + 1

    for i in range(1, n + 1):
        print(complited[i], end = ' ')

       

bfs(pre, complited)

위 코드는 메모리 초과가 떴다...

 

검색해보니 위상 정렬에 대해 알게되어서 위상 정렬 알고리즘을 이용해 코드를 다시 작성하였다.

 

<알고리즘>

1. 필요한 선수 과목 개수 진입차수 리스트인 degree에 해당 과목 번호 인덱스의 값으로 넣어준다.

2. degree 요소가 1인 인덱스는 선수 과목이 필요하지 않기 때문에 과목 번호를  queue에 넣어주고 result에 과목 번호 인덱스에 1을 넣어주었다

3. queue를 돌리며 해당 과목이 선수과목인 과목의 진입 차수를 -1 해준다

4. queue에 후수과목 번호를 넣는다

5. 해당 과목이 선수과목인 과목의 진입차수가 0이 되면 result에 과목 번호 인덱스에 해당과목의 학기 숫자 + 1을 넣어준다

 

## 위상정렬 이용 !

from collections import deque

n, m = map(int, input().split())

# 진입차수 리스트
degree = [0 for _ in range(n+1)]
# 선수조건 리스트
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    # 선수 조건 리스트
    graph[a].append(b)
    degree[b] += 1
    # 수강 완료 과목 리스트

def bfs(graph, degree):
    # 결과 리스트
    result = [0 for _ in range(n+1)]
    queue = deque()
    for i in range(1, n + 1):
        if degree[i] == 0:
            queue.append(i)
            result[i] = 1

    while queue:
        curr_nod = queue.popleft()

        for next_nod in graph[curr_nod]:
            degree[next_nod] -= 1
            if degree[next_nod] == 0:
                result[next_nod] = result[curr_nod] + 1
            queue.append(next_nod)
    
    for i in range(1, n+1):
        print(result[i], end = ' ')

       

bfs(graph, degree)

위 코드도 메모리 초과가 떴다...

 

계속 메모리 추가가 뜨는데 생각해보니 후수과목을 계속 queue에 넣지 않고 진입차수가 0일때만 넣어줘도 된다는 사실을 알게되었다.

 

최종 코드

## 위상정렬 이용 !

from collections import deque

n, m = map(int, input().split())

# 진입차수 리스트
degree = [0 for _ in range(n+1)]
# 선수조건 리스트
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    # 선수 조건 리스트
    graph[a].append(b)
    degree[b] += 1
    # 수강 완료 과목 리스트

def bfs(graph, degree):
    # 결과 리스트
    result = [0 for _ in range(n+1)]
    queue = deque()
    for i in range(1, n + 1):
        if degree[i] == 0:
            queue.append(i)
            result[i] = 1

    while queue:
        curr_nod = queue.popleft()

        for next_nod in graph[curr_nod]:
            degree[next_nod] -= 1
            if degree[next_nod] == 0:
                result[next_nod] = result[curr_nod] + 1
                queue.append(next_nod)
    
    for i in range(1, n+1):
        print(result[i], end = ' ')

       

bfs(graph, degree)

 

위 코드로 하니 성공 !!

 

정답이 안나올때보다 시간초과, 메모리 초과를 해결하는게 더 힘이 든다... ㅜㅜㅜ

 

https://www.acmicpc.net/problem/14567