728x90
https://www.acmicpc.net/problem/2252
처음 풀어본 위상정렬 문제이다!
위상정렬을 풀기 위해선 반드시 이용해야하는것이 있다.
1. 진입차수
2. 스택 또는 큐
3. 사이클 여부
각 노드를 가리키는 엣지가 몇개 인지(= 진입차수) 계산해주어야 하며, 스택 또는 큐 자료구조를 이용하고, 만약 그래프가 사이클이 존재할 경우에는 위상정렬 순서를 구할 수 없으므로 유의해주자.
또한 위상정렬을 푸는 알고리즘은 다음과 같다.
우선 배열에 입력을 저장해준 뒤, 배열을 탐색하여 진입차수를 계산함과 동시에 방향 그래프를 만들어준다.
그리고나서 진입차수가 0인 노드를 큐에 넣어준다.
이제 큐가 빌 때 까지 반복하는데, 우선 큐에서 노드 하나를 꺼낸다. 꺼낸 노드에 연결된 엣지들을 모두 제거한다.(제거 = 꺼낸 노드와 연결된 노드의 진입차수 1 감소)
그리고 만약 엣지 제거 이후 진입차수가 0이 되었다면 그 노드를 큐에 넣어준다.
큐에 있는 노드 하나를 탐색할 때 마다 해당 노드를 출력해주면, 그 결과가 바로 위상정렬 결과이다!
import sys
from collections import deque
input = sys.stdin.readline
def topology_sort():
while q:
num = q.popleft()
for i in graph[num]:
inDegree[i] -= 1
if inDegree[i] == 0:
q.append(i)
print(num, end = ' ')
n,m = map(int,input().split())
graph = [[] for _ in range(32001)]
arr=[]
inDegree = [0 for _ in range(32001)]
q = deque()
for _ in range(m):
big, small = map(int, input().split())
arr.append((big,small))
for big,small in arr:
inDegree[small]+=1
graph[big].append(small)
for i in range(1, n + 1):
if inDegree[i] == 0:
q.append(i)
topology_sort()
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/파이썬] 2166번 다각형의 면적 (0) | 2023.01.03 |
---|---|
[백준/파이썬] 9466번 텀 프로젝트 (1) | 2023.01.03 |
[백준/파이썬] 12852번 1로 만들기 2 (0) | 2022.12.30 |
[백준/python] 15684번 사다리 조작 (0) | 2022.12.26 |
[백준/파이썬] 18185번 라면 사기(small) (0) | 2022.12.22 |