CodingTest/Baekjun Online Judge

[ BOJ / 파이썬 ] 9466 텀 프로젝트

EEOOOO 2022. 8. 19. 13:50

 

cycle문제는 정말 간만이다.

 

 

문제 이해 포인트는 마지막에 DFS  순간이 정의되는 것을 찾는건데,

그 순간은 나(x)의 타겟이 cycle안에 존재해서 걔부터 시작해서 그 뒤에 얼마나 이어졌건간에 하여간 다 팀으로 인정하고 끝내는 것.

 

개인적으로는 내 타겟이 방문 안 된 상태일 때 어떤 액션을 취해줘야할 지 결정을 못 내려서 문제를 해결해내지 못 했었다.

같은 과정을 타겟에게 넘겨서 진행하며 반복하면 되는 것이었다.

언젠가 방문처리된 값에 도달할 수 있는데, 이 시점에서! 팀구성 가능한지를 체크하면 되는 것이다. 나는 이걸 반대로 하려고 해서 스스로 로직이 더 꼬였었다.

 

 

 

다시 정리하면. DFS에서는 아래와 같은 순서로 진행된다.

1) 나(x) 방문 처리

2) 내 타겟(내가 팀 하고 싶은 학생 설정)

3) 내 타겟의 방문완료 여부 확인? (내가 짝하고 싶은 애가 팀 구성 위해서 후보 그래프 안에 들어왔는지)

    방문완료 -> 
        -> 현재 모여있는 그룹 안에 존재하기도 해? ( 팀 구성의 첫 번째 친구인지 묻는 것.)

            -> 내 타겟부터 시작해서 끝까지 쭉 result에 넣기

    방문 No ->

        -> 내 타겟 기준으로 DFS진행

 

 

그리고 특히 하나 더 놓치지 말아야할 것은 resursion error 를 방지하기 위해 깊은 재귀 범위를 설정해주는 것.

 

 

import sys
sys.setrecursionlimit(111111) #충분한 재귀 깊이를 주어 오류를 예방

input = sys.stdin.readline


def dfs(x):
  global result
  visited[x] = True
  cycle.append(x)
  
  target = students[x]

  if visited[target]:
    if target in cycle:
      result += cycle[cycle.index(target):]
      return
  else:
    dfs(target)

for TestCase in range(int(input())):
  n = int(input())
  students = list(map(lambda x: int(x) - 1, input().split()))
  visited = [False] * n
  result = []
  for i in range(n):
    cycle = []
    
    if not visited[i]:
      cycle = []
      dfs(i)
  print(n - len(result))