[ 백준 ] 10451 번 순열 사이클 파이썬python 풀이

 

// 문제 요약

 

1부터 N 까지 정수로 만들 수 있는 순열의 한 가지 경우가 주어질 경우

 

1부터 N 까지 오름차순으로 정렬한 순열과

 

1대 1 대응 하여 만들 수 있는 그래프에서

 

순환 구조는 몇개가 생기는지 리턴하는 함수를 만들어라.

 

 

//사고

 

문제를 이해하는게 어려운 문제다.

 

문제의 참고자료를 보면 그림이 아주 잘 나와있는데

이런 행렬이 주어지면 첫번째 행이 from 두번째 행이 to 가 되는 그래프를 그릴 수 있다.

그려본다면 이런식이다.

 

모두 같은 숫자로 이루어진 순열이므로 뻗어나가고 끝나는 가지는 존재하지 않게 되고 순환구조가 발생하게 된다.

 

파이썬에서는 dfs를 이용하면 순환구조를 간단하게 찾을 수 있는 테크닉이 존재하는데

 

바로 파이썬의 set() 를 이용한 진행경로 추적이다.

 

dfs의 경우 깊이를 우선으로 탐색하므로

 

두갈래 혹은 세갈래 이상의 갈림길이 나타나면 그중 하나의 가지만을 선택해서 앞으로 나아간다.

 

그렇게 진행된 경로는 마지막 깊이까지 탐색한 후 종료되고

 

바로 직전의 갈림길에서 가지 않았던 길부터 다시 탐색한다.

 

따라서 각 재귀에서 뻗어나가는 가지가 모두 탐색이 되었다면

 

진행경로에서 해당 노드를 삭제한 후 함수를 마치면 성공적인 추적이 가능하다.

 

그리고 이번 문제는 몇개의 순환 고리가 존재하는지 알아내야하므로

 

한번 고리로 count된 구조에 속한 노드들은 다음 탐색에서 모두 제외되어야한다.

 

따라서 경로추적을 위한 se()와는 독립적으로

 

방문기록을 남기는 set()을 따로 만들어야 한다.

 

코드를 보자.

 

 

// 풀이

 

# beakjoon 10451

# Recursion limit을 늘려줘서 에러를 방지
import sys
sys.setrecursionlimit(100000)

# T개의 테스트를 풀어야 하므로 T번 수행한다.
T = int(input())
for _ in range(T):
    # 순열의 길이 N과 순열을 받아서 graph를 만든다.
    N = int(input())
    permutation = list(map(int, input().split(" ")))

    graph = {n + 1 : [permutation[n]] for n in range(N)}

    # dfs로 탐색하여 진행경로(trace)상에 있는 노드중에 한번 방문한 노드가 있다면
    # 순환구조로 판별하고 return한다. 진행경로는 갈림길마다 하나씩 reset 하므로
    # 해당 노드의 모든 갈래길을 다 탐색한 후에는 해당 노드를 지워주어야 한다.
    # 또 한번 탐색된 노드는 다시 방문했을때 순환구조가 중복 count 될 수 있으므로
    # 진행경로 추적을 위한 set 말고 방문 기록을 남기기 위한 set을
    # 추가적으로 만들어서 기록한다. 그리고 trace를 통해 순환 구조가 발견되면
    # count를 하나 증가시키면서 탐색을 마치고 visited에 의해 탐색이 마쳐질 경우는
    # count를 올리지 않아야 한다.

    visited = set()
    cicle_count = [0]
    def dfs(v, trace = set()):
        if v in trace:
            cicle_count[0] += 1
            return

        if v in visited:
            return

        visited.add(v)
        trace.add(v)
        for w in graph[v]:
            dfs(w, trace)
        trace.remove(v)

    for v in list(graph):
        dfs(v)

    print(cicle_count[0])

풀이 끝