[백준] 순열 사이클

문제보기 - https://www.acmicpc.net/problem/10451

문제명    - 순열 사이클

난이도    - S3

문제유형 - 그래프이론

풀이일자 - 25.03.15

 

📌 문제 탐색하기

• 주어진 순열을 그래프로 보고 사이클의 개수를 구하는 문제
• 순열은 1부터 N까지의 숫자가 포함되며 한 번씩 등장
  • 2 ≤ N ≤ 1,000
• 각 숫자는 자기 자신 또는 다른 숫자를 가리키며 방향 그래프를 형성
• 그래프의 순열 사이클의 개수를 구해야 함

 

 

🛠 시간복잡도 확인

• DFS(Depth First Search) 탐색으로 진행
• 최악의 경우 (T=1000, N=1000)일때 O(10^6)로 가능

 

📌 코드 설계하기

1. 하나의 사이클을 찾고 방문 표시하는 함수 생성하기
   • visited[current] = True로 방문 표시
2. 전체 순열에서 사이클 개수를 찾는 함수 생성하기
   • visited = [False] * (n + 1) 방문 체크 리스트
3. T , N 입력받기
4. 결과 출력하기

 

 

📌 정답 코드(1회차)

import sys

# 1. 하나의 사이클을 찾고 방문 표시하는 함수 생성하기
def find_cycle(start, perm, visited):
    current = start
    while not visited[current]:  # 방문하지 않은 노드일 때만 계속 탐색
        visited[current] = True
        current = perm[current]

# 2. 전체 순열에서 사이클 개수를 찾는 함수 생성하기
def count_cycles(n, perm):
    visited = [False] * (n + 1)
    cycle_count = 0

    for i in range(1, n + 1):
        if not visited[i]:  # 방문하지 않은 숫자라면 새로운 사이클 시작
            find_cycle(i, perm, visited)
            cycle_count += 1

    return cycle_count

# 3. T , N 입력받기
T = int(sys.stdin.readline().strip())

for _ in range(T):
    N = int(sys.stdin.readline().strip())
    perm = [0] + list(map(int, sys.stdin.readline().split()))  # 순열이 1부터 N까지의 정수를 사용
    
    # 4. 결과 출력하기
    print(count_cycles(N, perm))