백준 9466 텀프로젝트

문제 링크

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)
    

풀이하면서 막혔던 점과 고민

DFS에 대해서 모르는 개념들을 정리해보고 코드에서 오류가 나는 점을 스스로 고쳐보면서 아주 많은 시간을 들여서 열심히 공부해보는 데 의의가 있었으나...
답은 나오는데 백준 제출 프로그램에서는 시간초과가 뜨는 게 아쉽다.

이번 주에는 너무 시간이 없어서 다음에 고쳐보는 걸로... ㅠ

풀이 후 알게된 개념과 소감

DFS가 무엇인가에 대해서 더 생각해보는 시간이 되었다. 다음에 더 열심히 해봐야지 ㅠㅠ