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))