백준 / 줄 세우기 / 2252번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 줄 세우기 / 2252번 (골드 3단계)

문제 사이트: https://www.acmicpc.net/problem/2252

 

문제 설명

---

나의 풀이

N, M = map(int, input().split())

line = []

for _ in range(M):
    A, B = map(int, input().split())
    line.append([A, B])

result = []

result.append(line[0][0])
result.append(line[0][1])
del line[0]

for a, b in line:
    idx = 0
    for i in result:
        if b == i:
            result.insert(idx, a)
            idx = 0
            break
        else:
            idx += 1
    if idx > 0:
        result.append(a)
        result.append(b)

for re in result:
    print(re, end = " ")

풀이는 정답은 맞지만 for 반복문을 두 번 쓰게 되면서 시간복잡도가 초과가 되면서 시간초과가 발생했다.

from collections import deque

def topological_sort(N, graph, indegree):
    result = []
    queue = deque()

    # 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, N + 1):
        if indegree[i] == 0:
            queue.append(i)

    while queue:
        current = queue.popleft()
        result.append(current)

        # 현재 노드에서 이어진 간선을 따라가면서
        # 연결된 노드들의 진입차수를 감소시킴
        for neighbor in graph[current]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return result

# 입력 처리
N, M = map(int, input().split())

# 그래프 초기화
graph = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1)

# 간선 정보 입력
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    indegree[B] += 1

# 위상 정렬 실행
result = topological_sort(N, graph, indegree)

# 결과 출력
print(" ".join(map(str, result)))

---

※ 알아야 할 것

그래프를 이용하여 시간 복잡도를 줄여야한다.