[백준/dfs] 9466번: 텀 프로젝트

-문제:https://www.acmicpc.net/problem/9466

Gold level3 문제이다 

 

문제에서 팀을 이루는 경우는 두가지 인데, 

1) 자기 자신과 팀을 이루는 경우

2) 두명이상이고, 사이클을 이루는 경우

위 두 상황은 별개라고 생각해서 1)번을 특히 어떻게 구현해야 할지 잘 몰랐는데 1)번 경우도 사이클을 이루는 경우 이므로 

결과적으로 cycle을 이루는 것에 대해서만 함수를 작성하면 된다는 것을 구글링을 통해 알았다 

 

사이클이 되는 조건: 첫번째수 == 마지막 수가 가리키는 숫자

예) 4-7, 7-6, 6-4는 사이클을 이룬다. 6이 가리키는 숫자가 처음 시작인 4이기 때문

 

-정답풀이: 

import sys
sys.setrecursionlimit(111111)

def dfs(v):
    global result
    visit[v]=1
    cycle.append(v)#사이클을 이루는 팀을 확인하기 위해
    number=s[v]
    if visit[number]:
        if number in cycle: #사이클 가능 여부
            result += cycle[cycle.index(number):] #사이클 되는 구간 부터만 팀을 이룬다
        return 
    else:
        dfs(number)
        
for _ in range(int(input())):
    n=int(input())
    s=[0]+list(map(int,input().split()))
    visit=[1]+[0]*n
    result=[]
    for i in range(1,n+1):
        if not visit[i]:
            cycle=[]
            dfs(i)
    print(n-len(result))

-풀이 이해:

def dfs(v):
    global result
    visit[v]=1
    cycle.append(v)#사이클을 이루는 팀을 확인하기 위해
    number=s[v]
    if visit[number]:
        if number in cycle: #사이클 가능 여부
            result += cycle[cycle.index(number):] #사이클 되는 구간 부터만 팀을 이룬다
        return 
    else:
        dfs(number)

10번에 if number in cycle: 이 의미하는 것은 마지막 숫자가 가리키는 숫자가 cycle이라는 리스트 안에 있다면 그건 cycle을 이룬다는 것이다

그래서 number가 사이클의 시작이므로 number의 인덱스 부터 끝까지의 리스트를 result에 추가한다

사이클을 이루지 않는 경우는 다음 dfs를 실행하면 된다