처음문제를 풀당시 기존의 위상정렬에서 정점들의 선행순서를 위반하지만 않는다면 어떤 순서로 정렬해도 상관이 없었지만 14567, 선수과목 (Prerequisite) 문제에서는 각과목의 누적학기를 표시해 주어야 했다. 이걸 어떻게 누적시키지? 생각하며 재귀를 이용해야 하나? 라는 생각도 잠시 했었다. 하지만 심플하게 반복문을 돌면서 기존에 deque에 저장되어있던 학기정보인 cnt를 popleft하고 append하는 과정에서 자연스럽게 누적되는 학기수를 다룰수 있었다.
두 코드의 비교!
1. 전형적인 (위상)정렬 코드에서는 그래프를 표현하기위해 인접행렬을 사용하였지만 선수과목 문제에서는 사전과 리스트를 사용해 그래프를 표현하였다!
2. (위상)정렬 코드에서는 진입차수가 0인 정점을 저장하기 위해 vacantList라는 list를 사용하였지만 선수과목 문제에서는 Deque 내장형 자료구조를 사용하였다.
3.주목할 점은 선수과목문제에서 문제를 해결하기 위해 누적학기를 계산해 주었는데 이것을 Deque라는 자료구조에 튜플이라는 형식으로 데이터(정점을 나타내는 i,또는 v와 누적학기를 나타내는 cnt)를 저장하여 누적학기를 늘릴때마다 popleft하고 cnt+1을 append함으로써 해결하였다는 것이다!
#문제1 위상정렬
def topologicalSort(vertex, graph):
n=len(vertex)
inDegree=[0]*n
vacantList=[]
for i in range (n):
for j in range (n):
if(graph[i][j]>0):
inDegree[j]+=1
for i in range(n):
if(inDegree[i]==0):
vacantList.append(i)
while len(vacantList)>0:
v=vacantList.pop()
print(vertex[v], end=' ')
for u in range(n):
if(graph[v][u]>0):
inDegree[u]-=1
if(inDegree[u]==0):
vacantList.append(u)
vertex=['A','B','C','D','E','F']
graph=[[0,0,1,1,0,0],
[0,0,0,1,1,0],
[0,0,0,1,0,1],
[0,0,0,0,0,1],
[0,0,0,0,0,1],
[0,0,0,0,0,0]]
topologicalSort(vertex, graph)
#문제2. 선수과목문제 14567
import sys
import collections
from collections import deque
n,m=map(int, input().split())
ans=[0]*(n+1)#ans=정답을 반환하는 리스트
inDegree=[0]*(n+1)#inDegree=각정점의 진입차수를 표시하는 리스트
dq=deque()#위의 위상정렬 코드의 vacantList에 해당하는 진입차수가 0인 정점을 담기위한 Deque
arr=collections.defaultdict(list)#이것이 위의 비교 코드와는 가장 큰 차이점 같음. 그래프를 인접행렬이 아닌 사전(Dict)과 리스트로 표현함
for i in range(m):
a,b=map(int, input().split())
arr[a].append(b)
inDegree[b]+=1
for i in range(1, n+1):
if inDegree[i]==0:#진입차수가 0이면
dq.append((i, 1))#Deque에 삽입. 튜플의 형태(i, 1)로 Deque에 삽입하는 것 같음
ans[i]=1#1학기에 바로 이수 가능
while dq:#Deque는 이렇게만 코딩해 주어도 not dq.isEmpty()의 의미임
i, cnt=dq.popleft()
for v in arr[i]:
inDegree[v]-=1
if(inDegree[v]==0):
#deque에 cnt를 같이 넣어주는 것은 pop할때 마다 그 cnt를 1더하여 cur[i]에 저장하면서 누적학기를 계산해 주기 위함
dq.append((v, cnt+1))
ans[v]=cnt+1
print(*ans[1:])
###아래는 내가 풀다만 나만의 코드로 오직 그냥 한번 보고 한번 반성해보는게 그 의의의 전부!
# nap=list(map(int, input().split()))
# number=nap[0]
# prepos=nap[1]
==>> 굳이 list를 사용할 필요없이 n,m=map(int, input().split())으로 변수에 바로
받아낼수 있음.
# b=[]
# for i in range(prepos):
# b.append(list(map(int, input().split())))
==>>b는 조건들을 받아내깅 위한 리스트인데 collections.defaultdict를 사용하면
복잡한 코드를 매우간결하게 정리해 낼 수 있음
# vertex=[0]*(number+1)
# graph=[]
# for i in range(number+1):
# graph.append([])
# for j in range(number+1):
# graph[i].append(0)
==>>인접행렬이 아닌 defaultdict을 이용한 사전(dict)+리스트를 이용한 구조로 매우
간결하게 그래프를 표현할 수 있음
# for i in range(len(b)):
# graph[b[i][0]][b[i][1]]+=1
==>>이역시 defaultdict를 이용하면 매우 간결히 표현됨
# def topologicalSort(vertex, graph):
# n=len(vertex)
# inDegree=[0]*n
# # zeroVertex=[]
# for i in range(n):
# for j in range(n):
# if(graph[i][j]>0):
# inDegree[j]+=1
# # for i in range(1, n):
# # print(inDegree[i], end=' ')
# for i in range(n):
# if(inDegree[i]==0):
# zeroVertex.append(i)
# n=0
# while len(zeroVertex)>0:
# vs=[]
# n+=1
# while len(zeroVertex)!=0:
# vs.append(zeroVertex.pop())
# vertex[vs.pop()]=n
# for i in range(n):
# if(graph[v][i]>0):
# inDegree[i]-=1
# if(inDegree[i]==0):
# zeroVertex.append(i)
# topologicalSort(vertex, graph)