[백준] 9466 - 텀프로젝트 (G3)

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

9466번: 텀 프로젝트

사이클에 속하지 않는 노드의 개수를 세는 문제이다.

생각보다 최적화를 깐깐하게 요구했던 문제이다.

하지만 덕분에 내가 놓치고 있던 부분을 확실하게 바로잡을 수 있었다.

 

살면서 처음으로..!! python 그룹 언어에서 제일 빠르게 푼 사람이 되보았다 ㅋㅋㅋ

(21.12.17 오전 10시 30분 기준)

물론 저 32ms 차이는 크게 의미있는 차이는 아니지만.. 기분이 좋다 ㅎㅎ

 

이 문제의 알고리즘 분류는 DFS로 되어있는데, 위상정렬로도 간단하게 풀 수 있다.

위상정렬에서 사이클이 아닌 노드는 곧 진입차수가 0인 노드이기 때문이다.

즉, 위상정렬을 하면서 진입차수가 0인 노드를 매번 카운트하고, 그 결과를 출력하면 된다.

 

나는 계속 시간초과를 받았는데, 그 이유는 위상정렬을 비효율적으로 구현했기 때문이었다.

계산해보니 O(V+E) 가 나와야 할 위상정렬을 O(VE) 로 구현하고 있었다..

 

진입차수가 0인 노드를 뽑고나서, 해당 노드랑 연결된 노드들의 진입차수를 줄이기 위해

전체 진입차수 배열을 순회하면서 진입차수를 줄이고 있었던 것이다..

어차피 인접리스트를 쓰고있기 때문에, 그냥 인접리스트에서 얻은 값으로 바로 접근해서 줄이면 됐었다.

 

그동안 이걸 캐치하지 못했던 이유는, 다른 위상정렬 문제를 풀 때 이 방식의 구현으로도 너무 잘풀렸기 때문이었다.

이 문제의 빡빡한 테스트 케이스 덕분에 고칠 수 있었다

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    nums = [0] + list(map(int, input().split()))
    from_count = [0 for _ in range(n+1)]
    for num in nums:
        from_count[num] += 1

    d = deque()
    for i in range(1, n+1):
        if from_count[i] == 0:
            d.append(i)
            from_count[i] -= 1

    answer = 0
    while d:
        student = d.pop()
        answer += 1
        from_count[nums[student]] -= 1
        if from_count[nums[student]] == 0:
            d.append(nums[student])

    print(answer)