위상정렬 & 백준 2252 줄세우기

 

출처 백준 : https://www.acmicpc.net/problem/2252

 

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

2252번: 줄 세우기

1. 위상정렬

- 정해진 순서에 위반되지 않는 경우의 수를 정렬

- DAG(directed acyclic graph) 형태에서만 사용 가능하다(순환되면 안된다.)

- 선행된 조건이 이루어지지 않으면 발생할 수 없음

- 자동차를 만들기 위해 a,b부품이 필요할때 a 부품을 만들려면 또 다른 순서를 이행하여 조립하여야 한다.
때문에 자동차를 만들기 위해서는 a부품 조립 -> b부품 조립 - >자동차를 만들거나 b부품조립 -> a부품 조립 -> 자동차 조립을 해야한다

- 정해진 순서 조건만 맞으면 어느 위치에나 들어와도 상관없음

 

2. 방법

1. DFS & Stack

- DFS를 실행하면서 DFS가 끝나는 순서대로 기록하면 그 역순이 위상정렬이 됩니다.

출처 : https://jason9319.tistory.com/93

1. 순서도 1->2->5->7를 탐색후 더이상 갈데가 없어 stack에 [7,5,2]를 쌓아줍니다

2. 방문하지 않은 노드를 체크해주어 순서도 1->3->6를 탐색후 탐색이 완료하여 stack에[7,5,2,6,3]을 쌓아줍니다.

3. 순서도 1->4를 탐색 완료 후 stack[7,5,2,6,3,4]를 쌓고 마지막 1을 추가해줍니다. stack=[7,5,2,6,3,4,1]
4. 마지막 dfs는 탐색이 완료된 지점부터 쌓았기 때문에 반대로 차례대로 pop해줍니다.

5. result = [1,4,3,6,2,5,7]

 

2. Queue & 진입차수(indegree)

출처 : https://yjs03057.tistory.com/4

1. 진입차수가 0인 정점을 큐에 삽입

2. 큐에서 팝하면서 연결된 노드들의 간선을 -1

3. 간선이 제거되어 진입차수가 0이 된애들을 큐에 삽입

4. 큐가 빌때까지 위 과정을 반복

 

백준 2252번 문제 코드 풀이

## queue 방식을 이용하여 deque 불러옴 ##
from collections import deque
import sys

## vertex(점) edge(간선 정보를 저장)##
v,e = map(int, sys.stdin.readline().split())
## 들어오는 간선들을 일단 0으로 만듬 ##
## 0 1 2 3 4 ## vertex
## 0 0 0 0 0 ## 진입차수
in_dgree = [0] * (v+1)
## graph vertex가 어디에 연결
## 0 1 2 3 4 ##
##[][][][][] ##
graph = [[] for i in range(v+1)]

result = []
## graph vertex가 어디에 연결되있는지 체크 ## 백준문제 예제 기준
## 0 1 2 3 4 ##
##[][3][3][][] ## 1->3, 2->3이 연결되있다
for i in range(e):
    a, b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
##이때 연결된 간선 3번에 진입차수를 +1씩 해준다 ##
## 0 1 2 3 4 ## vertex
## 0 0 0 2 0 ## 진입차수
    in_dgree[b] += 1

def topology_sort():
    queue = deque()
## 진입차수가 0인 애를 찾아 queue에 넣어줌 ##
    for i in range(1,v+1):
        if in_dgree[i] == 0:
            queue.append(i)
## queue가 사라질때까지 반복 ##            
    while queue:
        node = queue.popleft()
## dfs와 달리 선입선출 FIFO시스템으로 순서가 바로 정렬된다 ##
        result.append(node)
## queue에서 -> result로 pop하면서 연결된 vertex에서 진입차수를 줄여준다 ##
        for i in graph[node]:
            in_dgree[i] -= 1
## 그리고 진입차수가 줄어든 vertex를 다시 queue에 삽입 ##
            if in_dgree[i] == 0:
                queue.append(i)

topology_sort()
print(' '.join(map(str,result)))