[백준] 10451. 순열 사이클 (+파이썬 코드)

Question. 백준 10451. 순열 사이클

 

 

 

---

Answer.

 

cycle의 개수를 세는 문제이다.

 

sol 1)

이 문제에서 배열의 번호(start node)와 배열의 값(destination node)을 이용해 graph를 만들었다.

위 문제에서는 인접행렬이나 인접리스트로 그래프를 만들 필요는 없어서 

일차원 배열로 graph를 만들었다.

 

그리고 union-find를 통해 cycle의 개수를 구하면 된다.

 

1) 배열의 번호가 start node를 의미하고, 배열의 값이 destination node를 의미하는 1차원 배열의 graph를 만든다.

graph = [0] + list(map(int, input().split()))

 

2) start node와 destination node의 parent가 같지 않으면, union 한다.

union_parent(parent, a, b)

 

3) start node와 destination node의 parent가 같으면, cycle의 개수를 1 증가시킨다.

if find_parent(parent, a) == find_parent(parent, b):
	cycle_cnt += 1

 

4) 2~3을 모든 edges에 대해 반복한다.

 

 

전체코드는 다음과 같다.

 

 

sol 1) 전체코드

import sys
input = sys.stdin.readline

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def cnt_cycle(graph, n):
    parent = [i for i in range(0, n+1)]
    cycle_cnt = 0

    for a, b in enumerate(graph):
        if a == 0:
            continue
        if find_parent(parent, a) == find_parent(parent, b):
            cycle_cnt += 1
        else:
            union_parent(parent, a, b)
    #print(parent)
    return cycle_cnt

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        N = int(input())
        graph = [0] + list(map(int, input().split()))
        answer = cnt_cycle(graph, N)
        print(answer)

 

 

sol 1)
Time Complexity	O(N+α(N))
Space Complexity	O(N)