[백준 9466번] 텀 프로젝트 (Python3)

import sys
input = sys.stdin.readline

def BFS(n):
  now = n
  while True:
    next = pick[now-1]
    if visited[now] != 0 and visited[now] != n:
      break
    if visited[now] == n:
      if team[now] == 1:
        break
      else:
        team[now] = 1
        now = next
        continue
    visited[now] = n
    if team[next] == 1:
      break
    now = next     
  
T = int(input())
for test in range(T):
  N = int(input())
  pick = list(map(int,input().split()))

  visited = [0]*(N+1)
  team = [0]*(N+1)
  for n in range(1,N+1):
    if visited[n] == 0:
      BFS(n)

  print(N-sum(team))

 

간단한 BFS 문제이다. 단방향 그래프가 사이클을 그리면 team이 성립한다는 뜻이므로 bfs를 돌렸을때 같은 지점을 두번 이상 방문시, team이라고 간주해주면 된다.

 

BFS를 돌려서 visited 리스트를 체크하고, 만약 이미 visited한곳을 또 지나가면 team의 멤버라는 의미의 team 리스트를 체크한다.

결과값은 전체 멤버에서 팀 멤버를 제외하면 된다.

 

 

알고리즘 자체는 금방 생각해냈는데, 시간초과가 계속 나서 뭐가 문제인지 알아봤는데, pick 리스트를 편의를 위해 deque로 만들었던것이 문제였다. deque 함수의 특정 지점에 접근하는 시간복잡도가 O(N)이었던 것이다. 아무때나 deque를 사용하면 안되겠다.

 

 

오늘의 교훈) 원소를 읽는 경우에는 deque를 이용하지 말자