[Swift][DFS] 백준 1248번 (맞춰봐)

요구능력 : DFS 재귀

 

코드설명 : 

 

일단 문제를 이해해야하는데,,

예제입력 1에 적혀있는 -+0++++--+로 예를 들어 설명해보자.

규현이가 쓴 수가 A[]라는 배열에 4개가 저장되어 있다고 가정해보면

A[0]의 합, A[0] ~ A[1]의 합, A[0] ~ A[2]의 합, A[0] ~ A[3]의 합이 음수, 양수, 0으로 구분되어 저장되는 것이라고 보면된다.

예제 출력1처럼 -2 5 -3 1일 때 A[0]의 합, A[0] ~ A[1]의 합, A[0] ~ A[2]의 합, A[0] ~ A[3]의 합을 직접해보면 -+0+가 나오는걸 알 수 있다. 이후에도 A[1]의 합, A[1] ~ A[2]의 합, ... 이렇게 구해보면 문제에서 뭘 구해야하는지 이해가 갈것이다.

 

나는 처음에 result배열에 그냥 평범하게 중복순열로 구해서 depth == n 인 지점에서 이중 for문을 돌려서 시간초과가 발생했다.

DFS에서 이중 for문을 돌리면 거의 당연하게 시간초과가 발생하기 때문에

이런 문제에서는 비교대상이 있으면 depth == n 까지 가서 이중for문을 사용하지말고,

함수를 하나 만들어서 비교값을 넣는 시점에 값을 넣을 수 있는지 미리 체크하는게 시간복잡도를 줄이는데 효율적인 것 같다.

 

 

후기 : 시간초과 때문에 생각보다 어려운 문제이지만, 2중 for문을 써야할 때는 이렇게 처리를 해주면 된다는걸 다시한번 알게된문제

import Foundation
let n = Int(String(readLine()!))!
var s = Array(repeating: Array(repeating: "0", count: n ), count: n )
var count = 0
let read = readLine()!.map{String($0)}
for i in 0..<n{
    for j in i..<n{
        s[i][j] = read[count]
        count += 1
    }
    
}
var result = [Int]()
func check(_ idx: Int) -> Bool{
    var sum = 0
    for i in stride(from: idx, through: 0, by: -1){
        sum += result[i]
        if s[i][idx] == "+" && sum <= 0 {return false}
        if s[i][idx] == "-" && sum >= 0 {return false}
        if s[i][idx] == "0" && sum != 0 {return false}
    }
    return true
}
func dfs(_ depth: Int){
    if depth == n{
        print(result.map{String($0)}.joined(separator: " "))
        exit(0)
    }
    
    for i in -10...10{
        result.append(i)
        if check(depth){
            dfs(depth + 1)
        }
        result.removeLast()
    }
}
dfs(0)