Baekjoon Online Judge 9466번 파이썬

문제 링크
https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

dfs를 실행하고, 방문되지 않는 노드를 no_team에 추가한다.
그리고 순환의 시작점과 마지막이 같으면 no_team에서 제외하려고 했었다.
하지만, 순환하지 않으면서 다시 방문되지 않는 노드가  결과에 포함이 안되어 오답이었다.

잘못 작성한 코드

import sys
sys.setrecursionlimit(10 ** 6)

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

def dfs(start):
  global loop
  visited[start] = True
  next = numbers[start]
  if i == next:
    loop = i
  if not visited[next]:
    dfs(next)
    
for i in range(T):
  no_team = []
  loop = 0
  n = int(sys.stdin.readline())
  numbers = [0] + list(map(int,sys.stdin.readline().split()))  

  visited = [False] * (n+1)
  for i in range(1,n+1):
    if not visited[i]:
      dfs(i)
      no_team.append(i)
    if loop in no_team:
      no_team.remove(loop)
  print(len(no_team))

순환하는 노드들을 팀으로 구성시키고 그 팀의 구성원 수를 전체에서 빼는 방법으로 풀었다.


정답 코드

import sys
sys.setrecursionlimit(10 ** 6)

def dfs(start):
  global result
  visited[start] = True
  loop.append(start) # 순환하는지 확인하기 위해
  next = numbers[start]
  if visited[next]: #만약 방문했다면, 순환하는지 확인.
    if next in loop:
      result += loop[loop.index(next):] #순환 사이클이 시작되는 부분부터 result에 들어가게.
      return
  else:
    dfs(next)

T = int(sys.stdin.readline())
    
for i in range(T):
  n = int(sys.stdin.readline())
  numbers = [0] + list(map(int,sys.stdin.readline().split()))  
  visited = [False] * (n+1)
  result = []
  for i in range(1,n+1):
    if not visited[i]:
      loop = []
      dfs(i)
  print(n-len(result))