R (DFS & BFS) 9466번 텀 프로젝트

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())

def dfs(v):
    visited[v] = True
    trace.append(v)
    w = arr[v]

    if w in trace:
        result.append(w)
        return

    else:
        dfs(w)

for _ in range(N):
    M = int(input())
    arr = [0] + list(map(int, input().split()))
    visited = [False] * (M+1)
    result = []

    for i in range(1, M+1):
        if visited[i] == False:
            trace = []
            dfs(i)

        else:
            result.append(i)

    print(M - len(set(result)))

내가 작성한 코드이다. 개인 테스트할 때에는 정상적으로 돌아갔는데 제출해보니 메모리 초과가 떳다. 아마도 예외처리를 안해주고 모든 경우를 돌린다음 답을 도출해서 그럴 것이라고 생각이 된다.

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

K = int(input()) # test 수

def dfs(v):
    global result
    visited[v] = 1 # 방문한 정점 기록
    traced.append(v) # 탐색 경로 저장

    w = graph[v] # 다음 방문할 정점
    if visited[w] == 1: # 방문 가능한 곳이 끝났는지 체크
        if w in traced: # 탐색 경로에 다음 방문할 정점이 존재하면 순환
            result += traced[traced.index(w):] # 사이클이 되는 구간부터만 팀을 이룸
        return
    else:
        dfs(w) # 탐색 진행



for _ in range(K):
    V = int(input()) # 학생 수
    graph = [0] + list(map(int, input().split())) # 그래프 생성, 맨 앞에 [0]을 추가해 인덱스에 접근하기 편리하도록.
    visited = [0] * (V+1) # 방문한 정점를 담을 stack 생성
    result = [] # 팀을 구성한 학생 수


    for i in range(1, V+1): # 1번 학생부터 탐색 시작.
        if visited[i] == 0: # 방문한 정점이 아닌 경우에만 탐색 진행
            traced = [] # 탐색 경로 정보를 담을 stack 생성
            dfs(i)

    print(V - len(result))

참고한 블로그의 코드이다. 대체적으로 코드가 비슷하지만 재귀함수에서

result += traced[traced.index(w):]

을 통해 반복을 줄여주었다.

2022년 4월 27일 포스팅 업데이트..