BOJ : 10451 순열 사이클

문제

이전문제 에서 참고했던 예시들을 이용하였다.

1번 예시 활용

import sys

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    array = [0] + list(map(int, list(sys.stdin.readline().strip().split())))
    visit = [0] * (n + 1)

    group = 1
    cycle_count = 0


    for i in range(1, n + 1):
        isCycle = False
        while visit[i] == 0:
            visit[i] = group
            i = array[i]
        while visit[i] == group:
            isCycle = True
            visit[i] = -1
            i = array[i]
        if isCycle:
            cycle_count+=1
        group += 1
    print(cycle_count)

2번 예시 활용(recursive)

import sys
sys.setrecursionlimit(111111) # recursive limit을 증가시켜서 컴파일 오류를 막는다.

def dfs(s):
    # 이미 방문한 곳인지 확인
    if not visit[s]:
        global cycle
        # 방문한 거 표시해주기
        visit[s] = True
        cycle.append(s)
        # 새롭게 방문할 곳
        new = array[s]
        # 방문 안 한 곳이면 방문하기
        if not visit[new]:
            return dfs(new)
        # 방문했던 곳이면 cycle 안에 있는 지 확인해주고 cycle에 없으면 cycle 찾기 중단
        if new not in cycle:
            return False
        # idx = cycle.index(new)
        # cycle = cycle[idx:]

        return True

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    array = [0] + list(map(int, list(sys.stdin.readline().strip().split())))
    visit = [False] * (n + 1)
    count = 0

    for i in range(1, n + 1):
        cycle = []
        if dfs(i):
            count += 1
            # print(cycle)

    print(count)