[BOJ] 10451. 순열 사이클(Python) / DFS

10451번: 순열 사이클

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하는 문제

# 23분 소요

• 사용 알고리즘 : DFS
• 실버 1 문제로 구현이 오래 걸리지 않았다. 
• 방문 표시 배열 check과 총 사이클 갯수를 셀 cycle 변수를 만들었다.
• 가리키는 숫자 인덱스와 배열 인덱스를 일치시키기 위해 주어진 숫자 리스트를 받으며 앞에 [0]을 추가해줬다.
• 재귀로 현 숫자가 가리키는 다음 숫자를 확인하며 나아간다.
• dfs함수의 인자로 (현 숫자와 실제로 탐색 시작한 숫자)를 받아 탐색을 실행한다.
• 사이클 이루면 cycle += 1 해준다

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

# 재귀로 현 숫자가 가리키는 다음 숫자 확인
def dfs(startNum, originNum):
    global cycle
    nextNum = A[startNum]   # 현 숫자가 가리키는 다음 숫자
    if check[nextNum]:      # 이미 방문했다면 사이클 이루는지 확인
        if nextNum == originNum:    
            cycle += 1      # 사이클 이룬 것이므로 +1
            return
    else:   				# 첫 방문이라면 방문 표시
        check[nextNum] = 1
        dfs(nextNum, originNum)     # 재귀로 다음 숫자 확인

# main
T = int(input())
for _ in range(T):
    N = int(input())
    A = [0] + list(map(int, input().split()))
    cycle = 0
    check = [0] * (N+1)             # 방문 표시
    for start in range(1, N+1):
        if check[start]:            # 이미 방문한 곳이면 탐색 X
            continue
        check[start] = 1            # 새로 탐색 시작
        dfs(start, start)           # 이동할 숫자와 사이클 확인용 시작한 숫자

    print(cycle)

---

• 시간 : 228ms / 메모리 : 125983kb
• 고찰 : 어렵지 않은 dfs문제였다. Keep Going.