[Silver III] 10451 - 순열 사이클

 

문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\  3& 2&7&8&1&4&5&6 \end{pmatrix}와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 \begin{pmatrix} 1 & \dots & i & \dots &n \\  \pi_1& \dots& \pi_i & \dots & \pi_n \end{pmatrix} 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

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

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

입력

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

출력

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

예제 입력 1

2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8

예제 출력 1

3
7

---

# 풀이 방법

순열, 조합 이런 얘기가 나왔기 때문에 dfs로 접근했다

교재에서 풀었던 아이스크림 개수와 동일한데 그 경우는 좌표였고 이 경우는 좌표가 아니다.

 

dfs를 기존과 다르게 정의했더니 조금 헷갈렸다

굳이 그래프를 꼭 정의하지 않고도 permutation 안에서 해결이 가능하구낭

 

# 코드

복습ver: 굳이 perm까지 인자로 건네줄 필요는 없었다

# 2024-04-18 11:55-12:05
import sys
sys.stdin = open("input.txt","r")

T = int(sys.stdin.readline().strip())

def dfs(curr, visited):
    visited[curr] = True
    next = perm[curr]

    if not visited[next]:
        dfs(next, visited)
    
for _ in range(T):
    N = int(sys.stdin.readline().strip())
    perm = [0] + list(map(int,sys.stdin.readline().split()))
    
    visited = [False] * (N+1)
    cnt = 0
    for i in range(1, N+1):
        if not visited[i]:
            dfs(i, visited)
            cnt+= 1
    print(cnt)

import sys
sys.stdin = open("input.txt", "r")

def dfs(graph, v, visited):
    visited[v] = True
    next_v = graph[v]
    if not visited[next_v]:
        dfs(graph, next_v, visited)

T = int(sys.stdin.readline().strip())
for _ in range(T):
    N = int(sys.stdin.readline().strip())
    perm = [0] + list(map(int, sys.stdin.readline().split()))
    visited = [False] * (N + 1)

    cnt = 0
    for i in range(1, N + 1):
        if not visited[i]:
            cnt += 1
            dfs(perm, i, visited)
    
    print(cnt)

## 오류해결

import sys
sys.stdin = open("input.txt", "r")

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

T = int(sys.stdin.readline().strip())
for _ in range(T):
    N = int(sys.stdin.readline().strip())
    perm = list(map(int, sys.stdin.readline().split()))

    graph = [[] for _ in range(N + 1)]
    for i in range(N):
        graph[i+1].append(perm[i])
        if i + 1 != perm[i]:
            graph[perm[i]].append(i+1)

    visited = [False] * (N + 1)

    cnt = 0
    for i in range(1, N + 1):
        if not visited[i]:
            cnt += 1
            dfs(graph, i, visited)
    
    print(cnt)

음... graph리스트를 굳이 저장할 필요가 없었다

perm 배열만 있으면 이미 연결 정보가 다 있는 것이기 때문