[백준]1766 문제집 #위상정렬#pq

1.풀이

(1) 주어진 선후관계만으로 q와 graph를 구성한다

(2) q에 있는 요소 중 가장 작은(가장 쉬운)것을 pop하면서 진행한다 => heap을 쓴다.

​

* 두가지풀이

- 소스코드1(시간초과) : toNode와 fromNode를 사용. fromNode를 하나씩 삭제하고 fromNode가 비어있을때 pq에 넣음

- 소스코드2 (통과) : toNode와 들어오는 노드의 개수(cntParent)를 사용. cntParent 0이 될때 pq에 넣음

​

2. 소스코드

(1) 소스코드1 (python3 시간초과)

import heapq
N,M=map(int,input().split())

fromNode={}
toNode={}
for i in range(1,N+1):
    fromNode[i]=[]
    toNode[i]=[]

for _ in range(M):
    a,b=map(int,input().split())
    fromNode[b].append(a)
    toNode[a].append(b)

pq=[]
for i in range(1,N+1):
    if not fromNode[i]:
        heapq.heappush(pq,i)

ans=[]
while(pq):
    nowNode=heapq.heappop(pq)
    ans.append(nowNode)
    for conNode in toNode[nowNode]:
        # 이전노드 삭제
        fromNode[conNode].remove(nowNode)
        # 비어있으면
        if not fromNode[conNode]:
            heapq.heappush(pq,conNode)

print(*ans)

 

(2) 소스코드2 (통과)

import heapq
N,M=map(int,input().split())

toNode={}
cntParent=[0 for i in range(N+1)]
for i in range(1,N+1):
    toNode[i]=[]

for _ in range(M):
    a,b=map(int,input().split())
    toNode[a].append(b)
    cntParent[b]+=1

pq=[]
for i in range(1,N+1):
    if cntParent[i]==0:
        heapq.heappush(pq,i)

ans=[]
while(pq):
    nowNode=heapq.heappop(pq)
    ans.append(nowNode)
    for conNode in toNode[nowNode]:
        cntParent[conNode]-=1
        if cntParent[conNode]==0:
            heapq.heappush(pq,conNode)

print(*ans)