[백준] 줄세우기 복기

문제

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

처음 생각했던 로직

1)

• permutation으로 순열을 만든다.

• 그 순열이 맞는지 확인한다.

-> 메모리 초과

2) 위상정렬
이론만 보고 내 마음대로 구현했다.
-> 시간초과

# N명의 학생들을 키 순서대로 줄을 세우려고한다.
# 두 학생의 키를 비교하는 방법

# M: 키를 비교하는 회수
# A가 B 보다 앞에 와야 한다.



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


graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[b].append(a)

res = []
visited = [False] * (N+1)
while True:
    if len(res) == N:
        print(*res)
        break

    for i in range(1,len(graph)):
        if not visited[i]:
            if len(graph[i]) == 0:
                visited[i] = True
                res.append(i)
                break

            else:
                flag = True
                for n in graph[i]:
                    if not visited[n]:
                        flag = False
                        break
                if flag:
                    visited[i] = True
                    res.append(i)
                    break

-> 문제점 for 문을 너무 많이 돈다. 비효율적인 풀이

풀이

위상정렬

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

graph = [[] for _ in range(N+1)]
in_cnt = [0]*(N+1)


for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    in_cnt[b] += 1



start_v = []

for i in range(1, N+1):
    if in_cnt[i] == 0:
        start_v.append(i)

for s in start_v:
    for g in graph[s]:
        in_cnt[g] -= 1
        if in_cnt[g] == 0:
            start_v.append(g)

print(start_v)

• start_v가 마지막 for문을 돌면서 갱신된다. 하지만 for문을 그래도 진행되기 때문에 반복 탐색하지 않는다.

• 들어오는 노드 갯수가 0인 노드들은 한번 탐색하면 다시 탐색할 필요가 없다. 왜냐하면, 이미 연결 노드를 삭재했기 때문이다.