[백준] 10451번 문제 (순열 사이클) 파이썬(Python) 풀이

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

10451번: 순열 사이클

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def dfs(start, visited):
    visited[start] = True
    for i in graph[start]:
        if not visited[i]:
            dfs(i, visited)

for _ in range(int(input())):
    n = int(input())
    nodes = list(map(int, input().split()))

    graph = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)

    for i in range(1, n + 1):
        graph[i].append(nodes[i - 1])
        graph[nodes[i - 1]].append(i)

    count = 0
    for i in range(1, n+1):
        if not visited[i]:
            count += 1
            dfs(i, visited)

    print(count)

처음에 문제 설명이 무시무시하게 생겨서 살짝 겁이 났었는데..

읽어보니 그리 무시무시한 문제는 아니였다.

 

문제에서 N개의 노드가 주어지는데,

그 N개의 노드들을 1, 2, 3 ... N 번까지의 숫자들과 매핑을 해서 그래프를 만들고,

그렇게 만들어진 그래프를 DFS든 BFS든 완전탐색을 통해 그래프가 몇개의 그래프로 나뉘어져있는지 파악하면 된다.