[알고리즘/파이썬] 백준 2252 - 줄 세우기

문제

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

풀이

사이클이 없는 방향 그래프에서 방향성이 한 곳만을 향하도록 정렬하는... 위상정렬...이란다.

나는 위상정렬이라는 개념은 몰랐고 그래프를 통해서 풀면 되겠다 싶긴했는데 정답을 도출하기가 참 어려웠다 ㅡ ㅡ 

그래서 검색해보니 위상정렬의 대표적이 문제라더라.

https://youtu.be/xeSz3pROPS8

 

1. 진입 차수가 0인 모든 노드를 큐에 넣는다.

2. 큐가 빌 때까지 while문을 돌린다.

3. 반복문에서는 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거

4. 새롭게 진입 차수가 0이 된 노드를 큐에 추가

 

저기 위상정렬 유튜브를 보면 다 알려주긴 하지만... 

만약 a->b 라면 b로 진입하는 차수가 한 개 있는 것이므로 indegree[b]를 +1 해주고, 이런 식으로 했을 때 진입차수가 0인 아이들 먼저 정렬해줘야 하므로 indegree값이 0인 아이들 먼저 골라서 q에 넣어줘서 정렬해준다.

 

 

코드

from collections import deque

n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]
# 진입차수 체크
indegree = [0 for _ in range(n+1)]

for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    indegree[b] += 1

def solution():
    result = []
    q = deque()

    for i in range(1,n+1):
        if indegree[i] == 0:
            q.append(i)


    while q:
        a = q.popleft()
        result.append(a)

        for i in graph[a]:
            indegree[i] -= 1
            
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i,end=" ")

solution()