백준 10451 순열 사이클 - Swift

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

10451번: 순열 사이클

 

입력

첫째 줄에 테스트 케이스의 개수 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

 

풀이 방법

위의 표를 그래프로 나타내면 아래와 같습니다.

그래프 3개가 나오게 되네요.

그래프 탐색에는 2가지가 있죠? DFS 와 BFS

저는 DFS로 탐색을 해보겠습니다. 몇개의 순환 그래프가 있는지는 어차피 전부 돌아봐야 알기 때문에 DFS BFS 상관없을 것 같다는 게 제 생각입니다.

위와 같이 각 인덱스에 dfs를 한번씩 해보면(총 8번) 몇 개 순환 그래프가 몇 개 인지 알 수 있습니다.

 

코드 

let T = Int(readLine()!)!

func sol() {

    for _ in 0..<T {
        let N = Int(readLine()!)!
        let nums = readLine()!.split(separator: " ").map{ Int(String($0))! }
        var line = Array(repeating: 0, count: N+1)
        var visited = Array(repeating: false, count: N+1)
        var answer = 0
        
        for j in 0..<nums.count {
            
            line[j+1] = nums[j]
        }
        
        func dfs(start: Int) {
            var index = 0
            var queue = [start]
            
            while index < queue.count {
                let node = queue[index]
            
                if !visited[node] {
                    visited[node] = true
                    queue.append(line[node])
                }
                   
                index += 1
            }
        }
        
        for i in 1...N {
            if !visited[i] {
                dfs(start: i)
                answer += 1
            }
        }
        
        print(answer)
    }
}

sol()