[Python] 순열 사이클 - 백준 (BFS)

해당 글은 백준 10451번 문제 '순열 사이클'을 다룬다.

문제

https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

 

설명

BFS로 계속해서 순환하여 사이클을 개수를 구하는 문제이다.

방문하지 않았다면 bfs 함수를 돌아서 사이클을 확인하고, 방문했다면 이미 포함된 사이클이 있으므로 넘어간다.

 

코드

from collections import deque

def bfs(x):
    queue = deque([x])
    visited[x] = True
    while queue:
        x = queue.popleft()
        nx = arr[x]
        if visited[nx] != True:
            queue.append(nx)
            visited[nx] = True

T = int(input())
for t in range(T):
    n = int(input())
    arr = [0]+list(map(int, input().split()))
    visited = [False]*(n+1)
    result = 0
    for i in range(1, n+1):
        if visited[i] != True:
            bfs(arr[i])
            result += 1
    print(result)