문제:

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열(3,2,7,8,1,4,5,6)을 배열을 이용해 표현하면 다음과 같다. 

[그림1]

또는 Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 [그림1] 과 같이 나타냈다면, 임의의 노드 i에서 다른 노드 p로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프(3,2,7,8,1,4,5,6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클"이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N(2<=N<=1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력:

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

풀이방법:

 DFS를 사용해서 풀 수 있는 문제이다. 1번 노드부터 시작해서 노드를 방문할 때마다 check를 1로 바꾼다. check가 1인 노드를 만나면 dfs를 종료하고 answer를 하나 증가시켜 순열 사이클의 개수를 나타내도록 하였다. 

 처음에는 DFS 함수를 재귀적으로 구현하고 제출했는데 런타임 에러가 발생하게 되었다. 코드를 봐도 런타임 에러가 발생할만한 곳이 없었는데 찾아보니 자체 시스템 상으로 재귀의 최대 한도가 정해져 있는데 이를 넘어가면 런타임 에러가 발생한다고 한다. 따라서 이 한도를 수정해야하는데 sys 모듈에 sys.setrecursionlimit() 라는 함수를 사용하면 재귀의 깊이 한도(?)를 조절 할 수 있다고 한다. 따라서 이 값을 2000으로 설정하고 코드를 다시 제출해 보았는데 통과할 수 있었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
def dfs(x,check,path):
    if check[x]:
        return
    check[x]=1
    dfs(path[x]-1,check,path)
 
sys.setrecursionlimit(2000)
for i in range(int(input())):
    n=int(input())
    path=list(map(int,input().split()))
    check=[0]*n
    ans = 0
    for j in range(n):
        if check[j] ==0:
            dfs(j,check,path)
            ans+=1
    print(ans)
cs

문제링크:

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

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2667. 단지번호붙이기  (0) 2019.09.07
[BOJ]2331. 반복 수열  (6) 2019.09.06
[BOJ]10825. 국영수  (0) 2019.09.04
[BOJ]1373. 2진수 8진수  (0) 2019.09.03
[BOJ]9613. GCD 합  (0) 2019.09.02

+ Recent posts