텀 프로젝트 ( 9466 번 )

9466번: 텀 프로젝트

 

🧠 알고리즘

모든 노드를 순회하며 미방문 노드 DFS 탐색 수행, 방문 노드 ( groups, group_idx ) 기록
dfs중 사이클 확정 시, 해당 구간 길이만큼 teams_count 증감
최종.. (전체 인원 - teams_count) 으로 팀 없는 인원 수 출력

 

🧾 코드

import sys

def _dfs(idx):
    global teams_count
    next = n_list[idx - 1]
    
    if (visit[next - 1] == 0) and (next not in group_idx):
        visit[next - 1] = 1
        group_idx[next] = len(groups)
        groups.append(next)
        _dfs(next)
        
    elif next in group_idx: # 사이클 확정
        teams_count += len(groups[group_idx[next]:])
        

t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    n = int(sys.stdin.readline().rstrip())
    n_list = list(map(int, sys.stdin.readline().rstrip().split()))

    visit = [0] * n # 방문 체크
    teams_count = 0

    for i in range(1, n + 1):
        if visit[i - 1] == 0: # 미 방문시 스캔
            groups, group_idx = [i], {i: 0}
            visit[i - 1] = 1
            
            _dfs(i)
            
    print(n -teams_count)

 

⏱️ 시간 복잡도

for i in range(1, n + 1) : 각 노드를 방문 ( 선형 시간 복잡도 )
    _dfs() : 탐색 ( 선형 시간 복잡도 )
>> 방문 안한 노드만 dfs로 탐색.. 즉.. 실제 로직은 선형시간

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )