[백준-파이썬] 9466 텀프로젝트

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

 

 

import sys
from collections import deque
sys.setrecursionlimit(10**6)

def check(start, students):
    q = deque()
    q.append(students[start])
    team = []
    
    while q:
        now = q.popleft()
        team.append(now)
        if now < len(students) and students[now] not in team:
            q.append(students[now])
    
    if start in team:
        # print(team)
        return team
    else:
        return False

T = int(sys.stdin.readline())

for _ in range(T):
    nums = int(sys.stdin.readline())
    students = list(map(int, sys.stdin.readline().split()))
    students = [s-1 for s in students]
    team = []
    visited = [False]*(nums)
    
    for i in range(nums):
        if visited[i] == True:
            continue
        if i == students[i]:
            team.append(i)
            visited[i] = True
            continue
        temp = check(i, students)
        
        if temp:
            for t in temp:
                visited[t] = True 
                team.append(t)           
            
    # print(team)
    print(nums - len(team))

 

30프로대에서 시간초과가 난다. 왜냐면 check 함수 내에 있는 "students[now] not in team" 이 부분이 O(n)이기 때문에 전체적인 코드는 O(n^2)이 될 것이다.

불필요하게 계속 서칭하는 부분을 줄이고자 함수를 없앴고, visited를 방문 안함:0, 탐색중:1, 이미 탐색완:2 이렇게 바꿔서 코드를 완성했다.

 

import sys
sys.setrecursionlimit(10**6)

T = int(sys.stdin.readline())

for _ in range(T):
    nums = int(sys.stdin.readline())
    students = list(map(int, sys.stdin.readline().split()))
    students = [s-1 for s in students]
    team = []
    count = 0
    visited = [0]*(nums)
    
    
    for i in range(nums):
                  
        if visited[i] == 2:
            continue
        else:
            temp = []
            now = i
            
            while visited[now] == 0:
                visited[now] = 1
                temp.append(now)
                now = students[now]
            # print(temp)
            if visited[now] == 1:
                idx = temp.index(now)
                count += len(temp[idx:])
                # count += len(temp)
                for t in temp:
                    visited[t] = 2
                    
            elif visited[now] == 2:
                for t in temp:
                    visited[t] = 2
       # print(team)
    print(nums - count)

 

여기서 의문이 들 수 있는 부분은 idx = temp.index(now)일 것이다. 왜 이런 장치를 했냐면 맨 처음 시작과 다른 곳에서 사이클이 만들어 질 수 있기 때문이다.

예를 들어 [A B C D B] 이렇게 순환하면 B이전인 A는 사이클에서 제외이다. 따라서 이렇게 사이클을 도는 부분만 한 팀으로 처리해야한다.