Baek_9466

오랜만에 골드3이라는 나에게는 높은 난이도를 도전했으나... 실패했다ㅠ

import sys
input = sys.stdin.readline

T = int(input())


def dfs(i):
    global start
    global temp
    if not visit[graph[i]]:
        visit[graph[i]] = True
        start = graph[i]
        temp += 1
        dfs(graph[i])


for _ in range(T):
    answer = 0
    n = int(input())
    graph = [0]+list(map(int, input().split()))
    global_visit = [True]+[False]*n
    for i in range(1, n+1):
        if global_visit[i]:
            continue
        visit = [True]+[False]*n
        start = 0
        temp = 0
        dfs(i)
        global_visit[i] = True
        if start == i:
            answer += temp
            
            for i in range(1, n+1):
                if visit[i]:
                    global_visit[i] = True
    print(n-answer)

자체 구현은 금방 했다.
graph를 리스트로 그대로 사용했고 visit과 globalvisit을 활용해서 방문 후 사이클인 경우만 globalvisit에 visit을 옮겨서 답을 찾아내는 방식을 사용했다.

근데 문제는 역시나 시간초과가 났는데 이 안에서 아무리 고쳐도 결과적으로는 답을 찾을 수가 없어서 결국 다른 블로그들을 참고해야했다ㅠ

import sys
input = sys.stdin.readline
sys.setrecursionlimit(150000)
T = int(input())


def dfs(x):
    global result
    visit[x] = True
    cycle.append(x) 
    num = graph[x]
    
    if visit[num]:
        if num in cycle:
            result += cycle[cycle.index(num):]
        return
    else:
        dfs(num)



for _ in range(T):
    answer = 0
    n = int(input())
    graph = [0]+list(map(int, input().split()))
    visit = [True]+[False]*n
    result = []
    for i in range(1, n+1):
        if not visit[i]:
            cycle = list()
            dfs(i)
    print(n-len(result))

그래서 차용한 방법은 이 방법인데.... 문제는 모든 블로그들이 dfs안에 구조를 저거랑 똑같이 했다는 점이다. 처음 시작한 사람의 아이디어가 계속 내려온것인지.... cycle을 확인하는 방법은 저게 무조건 정답이라 저걸 그대로 외워야 하는지 참ㅠ

인상깊은 접은 cycle을 확인하는 법인데 cycle에 계속 append를 하고 만약 그 안에 x가 있는 경우.. 즉 다시 돌아온 경우 사이클 부분부터 그 뒤까지를 result에 넣는다. 이것이 시간단축에 큰 중요성인거 같은데....

문제는 2466이란 골드5의 사이클 구하는 문제에서는 이것이 내 원래 코드보다 더 느리게 작동한다는 것이다ㅠ 어느 장단에 맞춰야할지 어렵다..

사이클을 구성하는 코드를 배운 점에서 감사하다고 생각해야겠다.