문제
풀이
위상 정렬에 대한 문제이다. 순서를 세우는 알고리즘인데, 먼저 entry라는 배열을 선언해준다. 이 배열은 해당 index 앞에 몇개가 있는지를 나타내는 배열이다.
그 다음 연결 리스트를 표현하기 위한 graph를 2중 배열로 선언한다. graph[a].append(b)라는 의미는 a뒤에 b값이 있다는 소리이다.
input단계에서 뒤에 나오는 숫자의 호출 횟수를 세어 앞에 몇개가 있는지 확인한다.
queue를 선언해주고, 먼저 entry 값이 0인 것을 넣어준다.
그 이후, popleft()로 return 된 값을 출력해주고, 뒤에 있던 수들의 entry 값을 1씩 줄여준다. 이 때, 0이 되면 queue에 넣어주어 정답을 도출한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
from collections import deque
N, M = map(int, input().split())
entry = [0 for _ in range(N+1)] #앞에 몇개가 있는지 나타내는 배열 선언
graph = [[] for _ in range(N+1)] #링크드 리스트를 위한 이중 배열 선언
for _ in range(M):
a, b = map(int, input().split())
entry[b] = entry[b] + 1 #앞에 하나가 추가되었으므로 +1
graph[a].append(b) #링크드 리스트에 추가 -> graph[a][i] : a뒤에 i가 있다.
q = deque()
for i in range(1, N+1):
if(entry[i] == 0):
q.append(i) #앞에 아무것도 없는 것들 queue에 추가
while q:
current = q.popleft() #왼쪽 값 pop하고 return하는 함수 : popleft()
for i in graph[current]: #current를 지웠으니 뒤에 있는 것들의 앞에 몇개가 있는지 나타내는 배열 entry에서 -1씩 해줌
entry[i] = entry[i] - 1
if(entry[i] == 0): #만약 돌다가 앞에 0개가 있는 것을 발견하면 queue에 추가
q.append(i)
print(current, end = ' ') #그 current 요소 출력
