문제 설명
문제
1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면
(1 2 3 4 5 6 7 8
3 2 7 8 1 4 5 6) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.
순열을 배열을 이용해 (1…i…n π1…πi…πn) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.
Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.
N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.
출력
각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.
풀이 과정
- 그래프로 보면.. 1번 노드가 3번 노드와 연결되어 있다 이런식으로 해석 가능
- 노드 1~n번째 각각에서 연결된 노드가 사이클을 형성할때까지 이동해본다.
- dfs 사용
- 끝나는 조건 : 이동할 때 시작 숫자 = 순열[index]
- visited를 두어 방문했던 노드들을 다시 방문하지 않도록 처리한다.
소스 코드
import sys
input = sys.stdin.readline
T = int(input().rstrip())
def dfs(visited, sequence, start, current):
if visited[current] == True:
return False
visited[current] = True
if current == start:
return True
return dfs(visited, sequence, start, sequence[current])
for _ in range(T):
N = int(input().rstrip())
sequence = [0] + list(map(int, input().rstrip().split()))
visited = [False] * (N+1)
answer = 0
for i in range(1, N+1):
if visited[i] == False:
answer += 1
dfs(visited, sequence, i, sequence[i])
print(answer)
'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글
[ 4179 ] [BFS] 불! (0) | 2021.07.31 |
---|---|
[ 2331 ] 반복 수열 (0) | 2021.07.30 |
[ 2491 ] [DP] 수열 (0) | 2021.07.29 |
[ 17175 ] [DP] 피보나치는 지겨웡~ (0) | 2021.07.29 |
[ 14916 ] [DP] 거스름돈 (0) | 2021.07.29 |