(backjoon) 9466 텀 프로젝트 - python

BFS/DFS로 분류되어있던 문제다. 그래서 다른 접근방법을 생각못하고 계속 시간초과로 헤매였었다.

 

심지어 python 풀이를 찾을 수 없어 당황했었다.

 

문제의 난이도는 어려워 보이지 않아서 다른 방법을 생각해 보니 문제 특성상 위상 정렬로 풀이하면 간단히 풀릴 것 같다는 생각이 들었다.

 

아래는 풀이코드다.

 

import sys
from collections import deque

input = sys.stdin.readline

T = int(input().rstrip())
def BFS(start, node, visit, degree) :
    d = deque()
    d.append(start)
    cnt = 0

    while d :
        now = d.popleft()
        visit[now] = True
        cnt += 1
        parents = node[now]
        degree[parents] -= 1

        if degree[parents] == 0 :
            d.append(parents)

    return cnt

for _ in range(T) :
    N = int(input().rstrip())
    people = list(map(int, input().rstrip().split()))
    people.insert(0,0)

    degree = [0] * (N + 1)
    ans = 0
    visit = [False] * (N + 1)

    for i in range(1, N + 1) :
        parents = people[i]
        degree[parents] += 1

    for i in range(1, N + 1) :
        if visit[i]: continue

        if degree[i] == 0:
            ans += BFS(i, people, visit, degree)

    print(ans)

 

풀이 알고리즘

 

1. 자신이 원하는 사람의 차수를 1씩 증가시킨다.

 

2. 차수가 0인 사람을 탐색한다.

 

3. 차수가 0인 사람이 선택했던 사람 차수를 빼준다. 그 사람이 차수 0이 되면 큐에 추가 (위상 정렬 알고리즘)

-> 단말 노드를 지워나가며 Count 해준다. (단말 노드가 짝이 없는 경우이기 때문)

 

4. 위상정렬하면서 방문했던 노드는 건너뛴다.