[알고리즘] Swift -백준 #10451(순열 사이클) -DFS

문제링크

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

10451번: 순열 사이클

 

문제

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

와 같다.

또는,

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

순열을 배열을 이용해 

로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

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

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

입력

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

출력

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

 

 

---

분석

1부터 n까지의 순열에서 사이클의 개수를 구하시오

 

풀이 과정

t = 테스트 케이스

t만큼 반복

• n = 순열의 크기
• 순열

테스트 케이스마다 순열에 대한 사이클의 개수를 출력

 

 

풀이

let t = Int(readLine()!)!

for _ in 0..<t {
    let n = Int(readLine()!)!
    let numArr = readLine()!.split(separator: " ").map{ Int($0)!}

    var lineArr = Array(repeating: 0, count: n+1)
    var checkArr = Array(repeating: false, count: n+1)
    
    for i in 0..<n {
        lineArr[i+1] = numArr[i]
    }
    
    func dfs(_ num: Int) {
        if !checkArr[num] {
            checkArr[num] = true
            dfs(lineArr[num])
        }
    }
    
    var count = 0
    for i in 1..<n+1 {
        if !checkArr[i] {
            dfs(i)
            count += 1
        }
    }
    print(count)
}

 

결과

 

 

---

📂  정리

해당 문제는 그래프에서 사이클을 찾는 문제이다.

방향 그래프에서 사이클이 존재하는 경우는 역방향 간선이 존재할 때이다.

역방향 간선의 개수 = 사이클의 개수

 

DFS 탐색을 하면서 DFS가 실행될 때마다 count값을 올려주면 사이클의 개수를 알 수 있다.

DFS 순회하면 연결된 노드들은 모두 방문하기 때문에
DFS한번에 사이클 한번을 순회한다.

 

사이클 개수 구하는 방법

배열이 2가지가 필요하다. 
1) 방문체크 배열
2) 해당 노드에서 종료되었는 지에 대한 여부를 저장하는 배열

 

 

 

 

 

 

 

 

 

[참고자료]

DFS 알고리즘 유튜브

https://www.youtube.com/watch?v=-rcHMKIBo1E&t=5s