[BOJ 2252] 위상정렬 알고리즘

위상정렬 알고리즘을 알게 된 후 푼 첫번째 문제.
위상정렬을 하기 위한 큐는 그냥 리스트를 사용했다.
(따로 pop하지 않고 그냥 시작 인덱스를 하나씩 늘려주는 방식)

방식을 간단히 설명하면

• 연결된 간선의 수를 기록하는 리스트 (chk)
  - chk[x] = x의 선행요소의 개수
• 선후관계에 대한 인접리스트 (arr)
  - arr[선행요소] = [후행요소들]
  코드를 보면 알 수 있지만, 이 두가지의 리스트를 이용했다.

1. 우선 간선의 수가 0인 노드를 큐에 넣고 시작한다.

2. 큐에서 원소 하나를 빼서 출력한 후, 해당 노드를 선행요소로 하는 후행요소들의 간선의 수를 하나씩 줄여준다.

3. 다시 간선의 수가 0이 된 노드를 찾아 큐에 넣고 반복. (1~2) 반복

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n, m = map(int, input().split())
chk = [0]*n
arr = [list() for _ in range(n)]

# 입력 받기 & 간선 기록
for _ in range(m):
    a, b = map(int, input().split())
    chk[b-1] += 1
    arr[a-1].append(b-1)

idx = 0
que = []

# 선행요소가 0인 원소들 큐에 넣기
for i in range(n):
    if chk[i] == 0:
        que.append(i)
        chk[i] -= 1

while idx < len(que):
	# 출력
    print(que[idx]+1, end=' ')
    # que[idx]을 선행요소로 갖는 원소들마다 chk 값을 하나씩 줄여줌
    for j in arr[que[idx]]:
        chk[j] -= 1
    idx += 1
    # 새롭게 chk가 0이 된 것들을 큐에 넣어줌 - 시간초과 발생
    for i in range(n):
        if chk[i] == 0:
            que.append(i)

이렇게 해서 되나 싶었는데, 결론부터 말하면 안됐다.

시간초과가 나서,pypy3로 다시 제출을 해볼까 하다가 매번 리스트를 순회하는 것에서 오류가 났겠다 싶어서 코드를 수정해서 제출했다.

상단 코드의 마지막 부분에서, 매번 탐색을 통해 chk값이 0인 원소를 고르는 방식이 문제였다.

while idx < len(que):
    print(que[idx]+1, end=' ')
    for j in arr[que[idx]]:
        chk[j] -= 1
        if chk[j] == 0:
            que.append(j)
    idx += 1

간선의 수를 줄여줄 때마다 0이 되었는지 확인하는 방식으로 수정했더니 성공했다.

작년 3월쯤 남긴 기록인데, 알고리즘이야 간단하지만 그냥 코드 자체가 수정할 부분이 많이서 리팩토링을 한번 거쳐보았다. 일단 굳이 왜 큐를 안 쓰고 있었는지 모르겠다. 사실 메모리 초과가 날 정도는 아니라는 믿음 + 라이브러리 찾기 귀찮음... 이 한 몫하는거 같은데, 기능이 비슷하다고 하더라도 가독성이 떨어지는 방법이었던 것 같다.

import sys
from collections import deque
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

def topological_sort(arr, chk):
    answer = list()
    que = deque()
    
    # 선행요소가 0인 원소들 큐에 넣기
    for i in range(1, n + 1):
        if chk[i] == 0:
            que.append(i)

    while que:
        # que[idx]을 선행요소로 갖는 원소들마다 chk 값을 하나씩 줄여줌
        for x in arr[que[0]]:
            chk[x] -= 1
            # 새롭게 chk가 0이 된 것들을 큐에 넣어줌
            if chk[x] == 0:
                que.append(x)
        answer.append(que[0])        
        que.popleft()
    
    return answer


if __name__ == "__main__":
    # 입력
    n, m = map(int, input().split())
    chk = [0] * (n + 1)
    arr = [list() for _ in range(n + 1)]

    # 입력 받기 & 간선 기록
    for _ in range(m):
        a, b = map(int, input().split())
        chk[b] += 1
        arr[a].append(b)

    # 연산 & 출력
    print(*topological_sort(arr, chk))