백준 14567 선수과목

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

14567번: 선수과목 (Prerequisite)

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

3 2
2 3
1 2

예제 출력 1 복사

1 2 3

예제 입력 2 복사

6 4
1 2
1 3
2 5
4 5

예제 출력 2 복사

1 2 2 1 3 1

 

풀이 : 

 

처음보는 위상정렬이다. 

사이클 없는 / 방향 그래프의/  모든 노드를/  방향성에 거스르지 않도록 순서대로 나열하는 것이다. 

 

다음의 여러 조건이 있다. 구현으로 풀어보려 했으나 쉽지 않다. 

 

동빈나 씨의 수업을 참고했다.

https://www.youtube.com/watch?v=xeSz3pROPS8 

다음과 같이 고급 알고리즘을 수강하려면 들어오는 두개의 간선, 즉 자료구조 알고리즘을 모두 수강해야 한다. 

또한 자료구조 > 알고리즘 > 고급 알고리즘 , 즉 자료구조 후 바로 고급 알고리즘 수강은 불가능하다. 

 

진입 차수(Indegree): 특정한 노드로 들어오는 간선의 개수 

진출 차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수

위상 정렬 

dfs 혹은 큐로 구현을 한다. 동작 과정은 다음과 같다. 

1. 진입 차수가 0인 모든 노드를 큐에 넣는다. 

2. 큐가 빌 때까지 다음의 과정을 반복한다. 

- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 

- 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다. 

즉, 큐에 들어온 각 노드의 순서가 위상 정렬을 수행한 결과와 동일 하다. 

 

(사이클에 포함되는 노드가 있으면 해당 진입 차수가 모두 0이 될 수 없다. $\rightarrow$ 위상 정렬 불가능)

 

 

여러 가지 답이 존재할 수 있다. 

한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우 여러 가지 답이 존재. 

(큐에 들어가는 순서 차이)

 

모든 원소를 방문 전, 큐가 빈다면 사이클이 존재 

(사이클 포함된 원소 중 어떤 원소도 큐에 못들어감)

 

스택을 활용한 DFS 이용으로도 구현 가능 

 

유의할 점 

list 를 print(end = ' ')로 출력하는 법 

*list 

 

몇번째 학기에 듣는지 확인하기 위하여, 다음 노드를 방문 했을 때, 그 전 노드보다 index +1 (중복되지 않도록 그 전 노드의 index에 +1을 한다.)

import sys
input = sys.stdin.readline
from collections import deque

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

graph = [[] for _ in range(n+1)]

indegree = [0] * (n+1)

for i in range(e):
    s , e = map(int, input().split())
    graph[s].append(e)
    indegree[e] += 1


answer = [0] * n
q = deque()

for i in range(1, n+1):
    if indegree[i] == 0:
        answer[i-1] = 1
        q.append(i)


while q:
    tmp = q.popleft()
    for j in graph[tmp]:
        indegree[j] -= 1
        answer[j-1] = answer[tmp-1]+1
        if indegree[j] == 0:
            q.append(j)
    


print(*answer, ' ')