[백준알고리즘] 10451번: 순열 사이클 -Python

[백준알고리즘] 10451번: 순열 사이클 -Python

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

10451번: 순열 사이클

수열이 주어지면 해당 수열에서 사이클이 몇 개나 형성이 되는지 찾는 문제이다.

 

먼저, 이 문제를 풀 떄 한 가지 고려하면서 풀었는데, 문제를 풀고 다른 분들의 코드를 보고서 의아했던 점이 있다. 내가 바보 같았던 점이긴 한데 요청 게시판에서 다른 분들도 올린 것을 보고 알게 되었다.

 

이 문제를 보자마자 다음과 같은 반례가 있을 것이라고 생각을 했다. 길이가 5로 주어졌을 때 1개의 사이클이 형성되는 것이다.

3->4->1->2->5->5

 

이런 식의 순열이 주어짐으로써 5에서만 사이클이 형성되는 경우를 생각했고, 이러한 방식으로 돌아가지 못하는 코드들이 있었길래 놀랐던 것이다. 하지만 내가 테스트 케이스를 직접 입력도 해봤음에도 요청 게시판을 보고 나서야 알았다니 창피하긴 한데... 저 사이클을 이루기 위한 입력을 구하면 다음과 같이 된다.

idx 1 2 3 4 5

val 2 5 4 1 5

 

보시다시피 값에 5가 두 번 들어가는 2 5 4 1 5가 된다. 이 값은 1~5의 값으로 이루어진 순열이 아니게 된다. 따라서 이 경우는 생각할 필요가 없다...

 

그래서 사실 visit[i] = idx 를 할 필요 없이 visit[i] = 1 을 해주어 방문 여부만 체크해주면 되는 것이었다. 방문했던 정점을 다시 방문한 경우에는 그 순간 사이클이 형성되는 것이기 때문이다. 따라서 하나의 정점씩 방향대로 이동하며 점검해주는 DFS 방식을 적용해주면 된다. 그러다가 방문했던 정점이 나오게 되면 사이클이 형성된 것이다.

import sys

testcase = int(sys.stdin.readline())
for _ in range(testcase):
    n = int(sys.stdin.readline())

    def get_cnt():
        cnt = 0
        sequential = [0] + list(map(int, sys.stdin.readline().split()))
        visit = [0] * (n+1)
        for idx in range(1, n+1):
            i = idx
            while not visit[i] and idx != visit[i]:
                visit[i] = idx
                i = sequential[i]
            if idx == visit[i]:
                cnt += 1
        return cnt

    sys.stdout.write("{}\n".format(get_cnt()))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다