[백준] 2252 - 줄 세우기 (Python)

[백준] 2252 - 줄 세우기

• https://www.acmicpc.net/problem/2252
• 알고리즘:
  • 그래프 이론
  • 위상 정렬

풀이

from collections import deque

N,M=map(int,input().split())
graph=[[] for _ in range(N+1)] #인접리스트
indegree=[0]*(N+1)

queue=deque()
result=[]

for i in range(M):
    a,b=map(int,input().split())
    graph[a].append(b)
    indegree[b]+=1 #진입차수 구하기

def topologicalSort(): #bfs로 구현
    for i in range(1,N+1):
        if indegree[i]==0:
            queue.append(i)

    while queue:
        V=queue.popleft()
        result.append(V)
        for i in graph[V]:
            indegree[i]-=1
            if indegree[i]==0:
                queue.append(i)

topologicalSort()
for num in result:
    print(num, end=' ')

처음에 인접행렬로 구현하여 문제를 풀었을 때 메모리 초과 문제가 발생했었는데, 인접리스트로 다시 풀고난 후 메모리 초과 문제를 해결할 수 있었다.

---

📌 Topological Sort(위상정렬 알고리즘)은 DFS / BFS를 통해 구현할 수 있다.

• DAG(Directed Acyclic Graph), 방향성은 있고 사이클은 없는 그래프에서 성립
• DFS로 구현하는 경우 탐색 결과의 역순이 위상 정렬이 됨

• algorithms