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

문제

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

10451번: 순열 사이클

풀이

간선의 비용이 전부 1로 같기 때문에 BFS를 사용했습니다.

딕셔너리 타입의 edges 변수에 (현재 노드: 연결된 다음 노드)의 형태로 값을 push합니다.

BFS로 사이클의 갯수를 셉니다. 사이클을 찾으면 사이클 안에 포함된 노드들을 cycle_components 리스트에 넣어서 다음 사이클 탐색시 이미 사이클로 판명된 노드를 재연산하지 않도록 합니다.

코드

import sys
from collections import deque


def bfs(n, edges):
    cycle_cnt = 0
    cycle_components = []
    for i in range(1, n + 1):
        if i in cycle_components:
            continue
        q = deque([i])
        temp = [i]
        while q:
            node = q.popleft()
            if edges[node] == i:
                cycle_cnt += 1
                cycle_components += temp
                break
            temp.append(edges[node])
            q.append(edges[node])
    return cycle_cnt


t = int(sys.stdin.readline().rstrip())
answer = []
for _ in range(t):
    n = int(sys.stdin.readline().rstrip())
    lst = list(map(int, sys.stdin.readline().rstrip().split()))
    edges = dict()
    for i in range(len(lst)):
        edges[i + 1] = lst[i]
    answer.append(bfs(n, edges))
for i in answer:
    print(i)