[알고리즘] 위상정렬(그래프 정렬)
(문제) 위상정렬(그래프 정렬)
위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘입니다.
각각의 일의 선후관계가 복잡하게 얽혀있을 때 각각 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘입니다.
만약 아래와 같은 일의 순서를 각각 지키면서 전체 일의 순서를 정한다면
1 4 //1번일을 하고 난 후 4번일을 해야한다.
5 4
4 3
2 5
2 3
6 2
전체 일의 순서는 1, 6, 2, 5, 4, 3과 같이 정할 수 있다.
전체 일의 순서는 여러 가지가 있습니다 그 중에 하나입니다.
입력설명
첫 번째 줄에 전체 일의 개수 N과 일의 순서 정보의 개수 M이 주어집니다.
두 번째 줄부터 M개의 정보가 주어집니다.
출력설명
전체 일의 순서를 출력합니다.
테스트케이스
입력예제 | 출력예제 |
---|---|
6 6 1 4 5 4 4 3 2 5 2 3 6 2 |
1 6 2 5 4 3 |
해결방법
- 입력을 손으로 그래프로 그려 본다.
- 진입 차수를 구한다.
(차수 : 노드의 각 연결된 선의 개수)
(진입차수 : 노드의 각 연결된 선 중에서 들어오는 것)
위의 예 같은 경우, 4는 진입차수가 2개이다 (1, 5) - dt라는 인접행렬을 만든다.
- 이 인접행렬을 입력으로 받은 값 중 2번 째 값이 나타내는 인접형렬의 인덱스를 +1 하여 초기화 한다.
- 큐를 생성하여 dt에 초기화 한 값들 중 0의 값이 들어있는 인덱스 번호를 append 한다.
- 큐에서 맨 앞의 값 하나를 꺼낸 후, 그 값을 출력한다.
- 출력한 값을 갖는 진입차 수들의 값을 -전부 -1 한다.
(1은 4의 진입차수 이므로 dt의 4번째 index 값을 -1 한다)
- 다시 큐에서 맨 앞에 값 하나를 꺼낸 후, 그 값을 출력하여 7번과 같은 방법을 이용하여 작동 시킨다.
- 이렇게 index의 값을 -1 할 때! 만약 index의 값이 0이 될 경우, 그 인덱스 번호를 다시 큐에 append 한다.
- 이 작업을 모든 degree가 0이 될 때 까지 반복한다.
동작 시각화
1. 입력을 가지고 인접행렬을 초기화 한다.
2. 초기화 한 인접행렬에 값이 없는 인덱스 번호를 “큐”에 삽입한다.
3. “큐”에 삽입한 인덱스 번호를 pop 하여 pop 한 값을 정답 리스트에 삽입하고, pop 된 인덱스 값을 가지고 있은 dt 값을 삭제를 한다.
4. dt값을 삭제를 한 후, 만약 값이 비면 비어진 dt 인덱스를 “큐”에 삽입한다.
5. 위의 작업을 “큐”에 아무것도 없을 때 까지 반복을 한다.
6. 끝나면 정답 리스트를 출력한다.
코드
from collections import deque
# n : 일의 개수
# m : 일 끼리의 연결 방법 개수
n, m = map(int, input().split())
# 어떤 인덱스가 진입 차수인지를 기억하기 위해서 2차원 리스트 사용
dt = [[] for _ in range(n)]
# 위상 정렬을 해결하기 위한 자료구조 큐 생성
dQ = deque()
# 정답 저장하는 공간
answer = []
for _ in range(m):
# s : 시작 노드
# e : 끝 노드
# s를 마쳐야 e를 할 수 있음
s, e = map(int, input().split())
# 진입차수를 저장 (-1 한 이유는 인덱스를 0에서 시작하기 위해서)
dt[e-1].append(s-1)
for i in range(n):
# dt의 값중 아무것도 진입 차수가 없을 경우
if len(dt[i]) == 0:
# 큐에 해당 인덱스 정보를 삽입
dQ.append(i)
while(dQ):
# 시작한 진입 차수
st = dQ.popleft()
# 정답 저장
answer.append(st+1)
for i in range(n):
# 있을 경우 삭제
if dt[i].count(st):
dt[i].remove(st)
# 만약 삭제하고 아무것도 없으면 해당 인덱스 큐에 저장
if len(dt[i]) == 0:
dQ.append(i)
print(*answer)
댓글남기기