[Swift] 백준_N과 M(9)(15663)

문제

 

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

15663번: N과 M (9)

 

 

풀이

 

지금까지의 N과 M문제들과는 달랐따..푸는데 너무 오래걸림. 

중복을 신경써야하는데 시간초과 안나는 방법이 떠오르지 않아서 다른 분들의 풀이를 참고해서 해결했다.

 

처음에는 DFS로 모든 경우를 만든 뒤 Set을 이용하고 정렬하여 출력해주었따. 누가봐도 시간초과 날 것 같은 코드다.

 

백트래킹을 이용하려면 중복되는 수가 들어왔을때는 넘어가도록 해야하는데 아이디어가 생각나지 않았다. 그러다 알게된 것이 마지막에 들어온 수를 저장하고, 만약 중복되는 수가 들어온다면 동일한 수가 들어올 것이므로 저장된 수와 비교해서 같은 수라면 dfs함수를 돌리지 않게 하였따.

 

처음에는 전역변수와 파라미터로 last값을 저장해보려고 했는데 잘못된 방법이었다.

dfs함수 내부에 지역변수로 last를 만들어 arr에 숫자가 추가될때 last의 값을 바꿔주었다. 이때 반드시 last에 값을 넣는 코드는 dfs를 실행시킨 이후에 추가해야한다.

그래야 각 depth별로 last값을 받을 수가 있기때문이다.

 

dfs는 깊이 우선 탐색이다. 그래서 만약 arr가 [1]이라면

[2]나 [3]일때의 dfs가 아닌 [1]에 숫자를 추가하면서 찾는 것이 우선이다. 그래서 같은 depth가 다르다면 last의 값이 겹칠 수 없다. [1]이 들어왔을때 last는 1이 되지만 아직 last가 바뀌지 않은채로 [1]에 대한 dfs함수들이 우선적으로 실행되기때문이다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let numbers = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted(by: <)
var check = [Bool](repeating: false, count: input[0])
var result: [[Int]] = []
func dfs(_ arr: [Int]) {
    var last = 0
    if arr.count == input[1] {
        result.append(arr)
        return
    }
    for i in 0..<input[0] {
        if !check[i] && last != numbers[i] {
            check[i] = true
            dfs(arr + [numbers[i]])
            last = numbers[i]
            check[i] = false
        }
    }
}
dfs([])
for num in result {
    print(num.map { String($0) }.joined(separator: " "))
}

 

 

_____________________________________________________________________________________________________

 

 

아이디어가 바로 떠올랐으면 좋겠다