백준 9466 텀프로젝트

NameError·2021년 5월 14일

문제 링크

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

풀이 전 계획과 생각

BFS와 DFS에 정말 자신이 없어서 이 문제가 너무나 어렵게 느껴졌지만... 기본적으로는 DFS로 '사이클'을 찾는다는 것은 DFS를 하다가 앞에 연결되었던 노드를 다시 만난 경우라고 할 수 있다.
즉 자기 자신을 선택한 경우에는 혼자 팀을 할 수 있다. 그러나 다른 친구를 선택한 경우는 그 친구가 선택한 다른 친구, 그 다른 친구가 선택한 또 다른 친구의 번호들을 돌고돌아서 자기 자신을 누군가 선택한 사이클이 형성되면 한 팀이 될 수 있고, 사이클이 형성되지 않고 서로 짝사랑만 했다면 그 라인은 모두 팀이 없이 버려진다.

즉, 선택한 학생들의 번호에 대한 DFS의 결과가 1→4→3→2→4라면 [1]은 버리고 4 이후부터 [4,3,2]가 팀에 속하게 된다.

따라서 기방문 여부를 기록하는 배열이 따로 있어야 하고
다음 번호의 기방문 여부가 1이라면

지금 DFS 중인 라인에 속해 있다면: 사이클을 형성한 것이니 해당 번호에서부터 팀을 잘라내면 됨
지금 DFS 중인 라인이 아니라 예전 라인에서 다른 DFS에서 방문한 것이라면: 아예 사이클이 끊어졌음. 이번 라인은 모두 팀 구성이 안 됨.

풀이 (코드 블록 첨부)

#백준 9466 텀프로젝트 

import sys

def DFS(now,choice,visit,selected):
    if visit[now]==0:
        visit[now]=1
        selected.append(now)
        
        return DFS(choice[now],choice,visit,selected)
        
    elif visited[now]==1:
        #print(now)
        #print(selected)
        if now in selected:
            return selected[selected.index(now):]
        else:
            return []


        
                 
        
        
    
T=int(sys.stdin.readline())
output=[]
for x in range(T):
    N=int(sys.stdin.readline())
    visited= [0 for y in range(N+1)]
    visited[0]=1
    choice_arr = [0]+list(map(int,sys.stdin.readline().split()))
    members=[]
    current_index=1
    #for current_index in range(1,len(choice_arr)):
    while 0 in visited and current_index<=N :

        if visited[current_index]==1:
            current_index+=1
            continue
        else:
            members+=DFS(current_index,choice_arr,visited,[])
            current_index+=1
            #print(members)
    output.append(N-len(members))
    
for element in output:
    print(element)