[백준/Python] #10451 순열 사이클

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

• Algorithm

순열이 주어졌을 때, 존재하는 사이클의 수를 출력하는 문제이다.  

문제에서 주어지는 순열 순서대로 graph에 넣어주면 [[3], [2], [7], [8], [1], [4], [5], [6]] 와 같은 그래프가 만들어진다.

우리는 존재하는 사이클의 수를 알고 싶기 때문에, bfs를 돌면서 모든 그래프를 방문할 때까지 시작점을 달리하여 반복해 주면 된다.

cycle_cnt = 0

    while (False in visited):
        start_p = visited.index(False)
        bfs(graph,start_p,visited)
        cycle_cnt+=1

즉, 반복문을 통해 bfs를 돌린후에 visited에 방문하지 않은 배열이 남아있다면, 배열에서 처음으로 False가 나오는 index부터 bfs를 해주면 된다. bfs가 끝나면 한 사이클이 종료된 것이므로 cycle_cnt를 증가시킨다.

• Code

import sys
input = sys.stdin.readline
from collections import deque

def bfs(graph, start, visited):
    queue=deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i-1]:
                queue.append(i-1)
                visited[i-1] = True

t = int(input())
for _ in range(t):
    n = int(input())
    line = list(map(int,input().split()))
    graph = []
    visited = [False]*n
    for i in range(n):
        graph.append([line[i]])

    cycle_cnt = 0

    while (False in visited):
        start_p = visited.index(False)
        bfs(graph,start_p,visited)
        cycle_cnt+=1
    
    print(cycle_cnt)