백준 - 순열 사이클(Swift)

백준 - 순열 사이클(Swift)

 

 

 문제 설명

 

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

10451번: 순열 사이클

 

 나의 풀이

 

처음 문제를 봤을때는 왜 3 2 7 8 1 4 5 6의 순열이 오른쪽처럼되는건지 이해를 하지 못했다.

이는 결국 1부터의 인덱스와 이 숫자들간에 간선이있음을 나타내는 것임을 알았고 사이클이 몇개 존재하면되는지를 확인하면 되기 때문에 재귀방법으로 문제를 해결했다.

 

하지만 어떠한 이유로 시간초과가 나서 문제를 해결하지 못했었는데 아래코드가 나의 처음 코드이다.

 

import Foundation

let tc = Int(readLine()!)!
var visited = [Bool]()
var arr = [Int]()
var result = 0
func cycle(_ num: Int) {
    visited[num] = true
    if !visited[arr[num]] { cycle(arr[num]) }
}

for _ in 0..<tc {
    let N = Int(readLine()!)!
    arr = Array(repeating: 0, count: N+1)
    visited = Array(repeating: false, count: N+1)
    let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
    for i in 1..<N+1 {
        arr[i] = input[i-1]
    }
    
    for i in 1..<N+1 {
        if !visited[i] {
            cycle(i)
            result += 1
        }
    }
    print(result)
    result = 0
}

 

cycle함수에서 현재 탐색중인 값을 방문표시하고 그 값이 가리키는 값이 방문되지않았다면 다시 사이클함수를 호출하는 방식으로 코드를 작성했었는데 이는 시간초과를 내기에 적합한 코드였다. 

예를들어 cycle함수가 연속으로 500번 호출되었다고 가정해보자.

그렇다면 첫번째부터 500번째까지 방문되지 않은 값들이었다는 것인데 이는 501번째에 방문했던 것이었다면 바로 모든 사이클이 종료가 되는것이 아니라 500, 499, 498번째의 함수가 순차적으로 끝나면서 종료하게 된다. 

즉 함수안에 함수안에 함수가 있는 형태였던 것이다. 

 

이를 다음의 코드로 해결할 수 있다.

방문되었다면 바로 return true를 줌으로써 함수를 종료시킬 수 있고, 방문되지않은 상태라면 return 함수를 줌으로써 함수안에 함수가 있는 것이 아닌 새로운 함수로 스코프가 이동되게 만들 수 있다. 

 

import Foundation

let tc = Int(readLine()!)!
var visited = [Bool]()
var arr = [Int]()
var result = 0
func cycle(_ num: Int) -> Bool {
    visited[num] = true
    if visited[arr[num]] { return true }
    return cycle(arr[num])
}

for _ in 0..<tc {
    let N = Int(readLine()!)!
    arr = Array(repeating: 0, count: N+1)
    visited = Array(repeating: false, count: N+1)
    let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
    for i in 1..<N+1 {
        arr[i] = input[i-1]
    }
    
    for i in 1..<N+1 {
        if !visited[i] {
            if cycle(i) {
                result += 1
            }
        }
    }
    print(result)
    result = 0
}