[백준] 줄세우기

출처:: www.acmicpc.net/problem/2252

분류:: 위상정렬

 

1. 문제 이해 및 해결과정

1->3  2 -↑ - 사이클이 발생하지 않고 순서가 정해져 있는 작업을 수행해야 하므로 위상 정렬을 이용하면 된다.

 

2. 풀이방법

#줄 세우기
#https://www.acmicpc.net/problem/2252
import sys
from collections import deque
sys.stdin = open("input.txt","r")
n,m=map(int,input().split()) #노드개수, 간선연결
graph=[[] for _ in range(n+1)]
indegree=[0]*(n+1) #진입차수
q=deque()
result=[]
for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    indegree[b]+=1

def topologysort():
    for i in range(1,n+1):
        #진입차수가 0인것 큐에 삽입
        if indegree[i]==0:
            q.append(i)

    while q:
        cur=q.popleft() #큐에서 뺄때마다 연관된 간선 없애주기
        result.append(cur)
        #cur과 연결되어 있는 진입차수를 1씩 뺀다
        for i in graph[cur]:
            indegree[i]-=1
            if indegree[i]==0:#진입차수가 0인것 계속해서 큐에 넣기
                q.append(i)

topologysort()
for x in result:
    print(x,end=' ')

 

3. 오답원인

 

4. 알게된 점

위상정렬

- 순서가 정해져있는 작업을 차례대로 수행할 때 사용하는 알고리즘 

- 임계경로를 구할 때 활용

- O(V+E) : 차례대로 모든 노드를 확인하면서, 노드에서 출발하는 간선을 차례대로 제거하므로