손가락놀이터

문제 후기

1. 이전에 프로그래머스에서 푼 순위라는 문제와 비슷하다고 생각했습니다. 아래에 링크를 남기겠습니다.
2. 순위에서 푼 방식대로 모든 사람의 해쉬를 만들고 비교한 값을 통해 갱신하는 방식으로 하니 메모리 초과로 틀렸고 알고리즘을 변경하기로 했습니다.
3. 알고리즘을 생각하다 DFS로 생각했고 문제를 풀었습니다.
4. DFS외에, 위상정렬이라는 것이 있는 것을 알게 됐고 모르는 방식이라 공부를 했습니다. terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093를 보고 위상정렬이 어떤 것인지 파악했습니다.
5. 위상 정렬 알고리즘으로 비교에서 큰 적이 없는 값부터 시작해서 DFS 방식으로 하나씩 차례대로 나아가는 방식으로 해결했습니다.

문제링크

from sys import stdin
from _collections import deque

N, M = map(int, stdin.readline().split())

num_dict = {}

for n in range(1,N+1):
    num_dict[n] = []


taller = [0] * (N+1)    # 큰 횟수
queue = deque([])       # 큐 생성


for _ in range(M):
    A, B = map(int, stdin.readline().split())
    # B에 큰 횟수를 저장
    taller[B] += 1
    # A에서 B로 갈 수 있도록 설정(DFS)
    num_dict[A].append(B)

# 비교에서 큰 적이 없는 값
for num in range(1,N+1):
    if taller[num] == 0:
        queue.append(num)
# 결과값
answer = []

# queue에 값이 있는 동안 반복
while queue:
    now = queue.popleft()
    # 결과값에 추가
    answer.append(str(now))

    # 간선 파악
    for i in num_dict[now]:
        # 1이면 queue에 추가
        if taller[i] == 1:
            queue.append(i)
        taller[i] -= 1
print(" ".join(answer))