BOJ_2252(줄세우기)

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

접근 방식

1. 사이클이 존재하지 않은 방향그래프에서 줄세우기를 하려면 위상정렬이 적절하다.
2. 문제에서 답이 여러가지인 경우가 있다고 언급했는데, 위상정렬의 결과는 여러개일 수 있다.

위상정렬 구현 방법

구현

from collections import deque
import sys
input = sys.stdin.readline

# 입력 및 그래프 생성
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
in_degree = [0] * (N + 1) # 진입 차수
for _ in range(M):
    s, e = map(int, input().split())
    graph[s].append(e)
    in_degree[e] += 1

# 위상 정렬
result = []
def topology_sort():
    que = deque()
    
    # 진입 차수가 0인 노드를 큐에 삽입
    for i in range(1, N + 1):
        if in_degree[i] == 0:
            que.append(i)
    
    # 위상정렬의 완전히 수행되기 위해 정확히 N개의 노드를 방문
    for _ in range(N):
        # N개를 방문하기 전에 큐가 비어있게 된다면 -> 사이클 발생
        if not que: return
        
        next = que.popleft()
        result.append(next)

        # 연결되어 있는 노드의 진입차수를 1 빼준다.
        for node in graph[next]:
            in_degree[node] -= 1
            # 새롭게 진입차수가 0이 된 노드를 큐에 삽입
            if in_degree[node] == 0:
                que.append(node)

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

위상 정렬을 사용하지 않은 풀이

python → 시간초과
pypy → 4400ms

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
result = []
used = [False] * (N + 1)
for _ in range(M):
    s, e = map(int, input().split())
    if not used[s] and not used[e]:
        # 둘 다 아직 사용되지 않았을 때
        result.append(s)
        result.append(e)
        used[s], used[e] = True, True
    elif not used[s] and used[e]:
        # 뒤에 오는 숫자만 사용되었을 때
        result.insert(0, s)
        used[s] = True
    elif used[s] and not used[e]:
        # 앞에 오는 숫자만 사용되었을 때
        result.append(e)
        used[e] = True
    elif used[s] and used[e]:
        # 둘 다 사용되었을 떼
        index1, index2 = -1, -1
        for i in range(len(result)):
            if result[i] == s:
                index1 = i
            if result[i] == e:
                index2 = i
            if index1 != -1 and index2 != -1:
                break
        # 스왚
        if index1 > index2:
            result[index1], result[index2] = result[index2], result[index1]
# 끝까지 사용되지 않은 수 처리
for i in range(1, len(used)):
    if not used[i]:
        result.append(i)

print(" ".join(map(str, result)))