[Swift] 백준_SHOW ME THE DUNGEON(25330)

문제

 

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

25330번: SHOW ME THE DUNGEON

 

 

풀이

 

처음에 DFS를 이용해 배열의 크기가 1인 것부터 n개인 것까지 미리 모두 구한 뒤에 각각의 케이스별로 계산해서 결과를 구했었다. 이렇게 했을때 시간 초과가 나와서 방법을 더 고민하다가 배열에서 k보다 큰 것들은 미리 빼놓으면 dfs를 돌릴때 많이 줄어들 수도 있다고 생각해서 다시 시도해봤는데 역시 큰 차이가 없어서 그런지 시간초과가 나왔다.

 

고민을 계속하던 중 알고리즘 분류에서 백트래킹이라는 것을 보고 한 번 시도해보았다.

 

백트래킹도 dfs처럼 모든 것을 탐색하는 느낌이지만, 진행하다가 더 이상 만족하는 조건이 없으면 해당 경로를 넘기고 이전으로 돌아가서 다음 경로로 시도하는 것이다.

 

처음에 dfs로 했을때는 모든 경우의 수를 구했기때문에 k보다 받은 데미지가 큰 경우들도 있었다. 근데 백트래킹으로 한다면 [5]가 들어왔을때 이미 k와 같아졌으므로 이후의 5로 시작하는 경우는 전부 무시되어 바로 다음으로 넘어갈 수 있었다.

 

 

나는 일단 N이 20밖에 안되기때문에 아예 k보다 큰 몬스터들을 제외하기 위해 newMonster라는 배열을 새로 만들어주었다. 마찬가지로 people배열도 바꿔주어야하므로 newPeople을 새로 선언하였다.

이때, newMonster가 비어있다면 사람을 구출할 수 없다는 것이므로 바로 0을 출력하고 종료시켜주었다.

 

 

solution함수는 재귀를 이용한 dfs와 거의 유사하다. 다만, 조건을 추가해주어 불필요한 경우를 제외하도록 해주었다.

 

일단, solution함수가 호출될때마다 damage가 k보다 작거나 같으면 result를 업데이트하였따. 이후에 damage가 크거나 같으면 함수를 종료하도록했는데, 만약 k와 같다면 이후에 더 이상 진행이 불가능하므로 두번째 조건에서도 등호를 넣어주었다.

 

다음은 0부터 newMonster의 개수만큼 반복하여 solution을 재귀적으로 호출해주었다. 이때, check[i]가 true라면 그냥 넘어가도록 하였고 만약 아니라면 check[i]를 true로 만들어준뒤 함수를 호출하고 다시 false로 바꿔주었다.

false로 바꿔주지않으면 모든 경우를 탐색할 수 없기때문에 해줘야한다.

 

 

그리고 시간을 최대한 단축하기 위해 라이노님의 입출력 클래스를 이용하였다.

import Foundation

final class FileIO {
    private var buffer:[UInt8]
    private var index: Int
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)]
        index = 0
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        
        return buffer.withUnsafeBufferPointer { $0[index] }
    }
    
    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true
        
        while now == 10
                || now == 32 { now = read() }
        if now == 45{ isPositive.toggle(); now = read() }
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }
        
        return sum * (isPositive ? 1:-1)
    }
    
    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()
        
        while now == 10
                || now == 32 { now = read() }
        
        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }
        
        return str
    }
}

let file = FileIO()

let n = file.readInt()
let k = file.readInt()
var monster: [Int] = []
var people: [Int] = []
for _ in 0..<n {
    monster.append(file.readInt())
}
for _ in 0..<n {
    people.append(file.readInt())
}
var newMonster: [Int] = []
var newPeople: [Int] = []
var result = 0
var check = [Bool](repeating: false, count: n)

for i in 0..<monster.count {
    if monster[i] <= k {
        newMonster.append(monster[i])
        newPeople.append(people[i])
    }
}
if newMonster.isEmpty {
    print(0)
    exit(0)
}
func solution(_ arr: [Int], _ damage: Int, _ resque: Int) {
    if damage <= k {
        result = max(result,resque)
    }
    if damage >= k {
        return
    }
    for i in 0..<newMonster.count {
        if !check[i] {
            check[i] = true
            var tempDamage = 0
            let newArr = arr + [i]
            for j in newArr {
                tempDamage += newMonster[j]
            }
            solution(newArr, damage + tempDamage, resque + newPeople[i] )
            check[i] = false
        }
    }
}
solution([], 0, 0)
print(result)

 

 

_____________________________________________________________________________________________________

 

아직 백트래킹 감이 잘 안온다. dfs를 구현했을때와 거의 동일하지만 맞는지도 잘 모르겠어서 더 풀어봐야 할 것 같다. 그래도 백트래킹이라는 알고리즘을 알게되어 만족