[위상 정렬] 백준 2252 줄 세우기

 

위상이 위치를 뜻한다고 한다

위상정렬은 각 노드들의 순서를 찾는 알고리즘이다

 

이 사진을 보고 바로 이해가 갔다.

0->1->2->4->3->5 순으로 진행해야 한다.

그림에서 보면 알겠지만 먼저 탐색을 시작하는 것은 진입차수가 0인 노드부터이다.

진입차수 배열을 따로 만들어서

1. 진입 차수가 0인 정점을 모두 큐에 삽입
2. 큐에서 정점를 빼며 진입차수를 감소시킴
3. 진입차수가 0이 됐다면 큐에 삽입

순으로 진행하면 일의 순서를 알 수 있게 된다

 

from collections import deque

def topology():
    q = deque()

    ##진입 차수가 0인 정점을 모두 큐에 넣는다
    for i in range(N):
        if cnt_input[i] == 0:
            q.append(i)

    while q:
        curr = q.popleft()
        print(curr + 1, end=" ")
        for node in graph[curr]:
            cnt_input[node] -= 1
            if cnt_input[node] == 0:
                q.append(node)

if __name__=='__main__':
    N, M = map(int, input().split()) #명수, 키를 비교한 회수
    visited=[False] *N
    graph=[[] for _ in range(N)]
    cnt_input=[0]*N

    for _ in range(M):
        a, b = map(int, input().split())
        a-=1; b-=1
        graph[a].append(b)
        cnt_input[b]+=1 #진입차수 증가

    topology()

먼저순서 -> 나중순서 순으로 탐색해야 하므로 graph[먼저순서].append(나중순서) 순으로 넣어줘야 한다.

진입차수는 말 그대로 화살표가 들어오는 차수이므로 그래프가 추가될때마다 나중순서의 진입차수를 1씩 증가시켜줘야 한다.

 

백준 줄세우기

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

 

 

 

모의 SW역량테스트 a형에 나왔었는데 위상정렬을 몰라서 틀렸다 ;ㅅ; 근데 풀어보니까 별 게 아니었다. 개념 모르고 힌트만 봤는데도 바로 풀려서 놀랐다. 다음에는 안 틀려야지.

 

 

Reference

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html