백준 14567 선수과목 - 골드5 [파이썬]

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

14567번: 선수과목 (Prerequisite)

 

이거 위상정렬 문제 맞나 의심이 돼서 DFS 비슷하게 풀어봤는데 택도없이 시간초과났다.

바로 어제 공부한게 위상정렬인데.. 막상 써먹질 못하다니 ㅠ

 

배운점

1. 2차원 배열로 그래프를 그리는게 아니라 collections 의 defaultdict 사용하는 방법도 있더라.

    - 근데 이거 쓰면 좀 더 느림

 

성공코드

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

N, M = map(int, input().split())
# graph = [[] for i in range(N+1)]
graph = defaultdict(list)
indegree = [0 for i in range(N+1)]
result = [1 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    # 방향그래프 그리고 진입차수 세기
    graph[a].append(b)
    indegree[b] += 1

queue = deque()
for i in range(1, N+1):
    if indegree[i] == 0:
        queue.append((i, 1))  # 정점 번호, count

while queue:
    now, count = queue.popleft()
    for i in graph[now]:
        indegree[i] -= 1
        if indegree[i] == 0:
            queue.append((i, count+1))
            result[i] = count + 1

print(" ".join(map(str, result[1:])))

# 위상정렬. 거기에 dp적인 요소를 첨가함.
# 2차원 배열 graph 말고 collections 의 defaultdict 을 사용하면 좀 더 편리 (그러나 시간은 더 늘어나더라)

 

괴상한 DFS로 풀었다가 실패한 코드

import sys
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
indegree = [0 for i in range(N+1)]
result = [1 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    # 방향그래프 그리고 진입차수 세기
    graph[a].append(b)
    indegree[b] += 1

queue = deque()
for i in range(1, N+1):
    if indegree[i] == 0:
        queue.append((i, 1))  # 정점 번호, count
        while queue:
            now, count = queue.pop()
            result[now] = count if result[now] < count else result[now]
            for j in graph[now]:
                queue.append((j, count+1))

print(" ".join(map(str, result[1:])))

 

결과