백준 15649 N과 M(1)

출처: https://www.acmicpc.net/problem/15649

분류: 백트래킹

---

접근방식

1~N까지의 수 중에서 중복없이 해당 길이의 모든 경우의 수를 다 찾는 문제였습니다.

가능한 모든 경우의 수를 다 고려하는 백트래킹으로 해결했습니다.

처음엔 원하는 길이만큼 만들어 나가는 dfs를 1~N을 시작점으로 해서 여러 번 돌리는 방식으로 풀었는데요

백트래킹을 공부하고 정통적인 방법으로 다시 풀어봤습니다.

 

해결방법

1 ~ N을 시작으로 해서 주어진 길이만큼의 배열을 만들어나가는 dfs 방식입니다.

protocol Readable {
    func readSingleValue() -> String
    func readArray(with separator: Character) -> [String]
}

extension Readable {
    func readSingleValue() -> String {
        return readLine()!
    }
    
    func readSingleValue() -> Int {
        return Int(readLine()!)!
    }
    
    func readArray(with separator: Character) -> [String] {
        return readLine()!.split(separator: " ").map { String($0) }
    }
    
    func readArray(with separator: Character) -> [Int] {
        return readLine()!.split(separator: " ").map { Int(String($0))! }
    }
}

// MARK: 백트래킹
class BOJ15649: Readable {
    
    func input() {
        let data: [Int] = readArray(with: " ")
        n = data[0]
        length = data[1]
    }
    
    // MARK: Properties
    
    var n: Int!
    var length: Int!
    
    // MARK: Solution
    
    func solution() {
        input()
        
        for i in 1...n {
            track(num: i, numbers: [i])
        }
    }
    
    func track(num: Int, numbers: [Int]) {
        guard numbers.count < length else {
            print(numbers.reduce(into: "", { $0 += "\($1) "}).dropLast())
            return
        }
        guard num <= n else { return }
        for i in 1...n where !numbers.contains(i) {
            track(num: i, numbers: numbers + [i])
        }
    }
}

BOJ15649().solution()

 

 

정통적인 백트래킹 풀이로 isUsed 변수를 사용해 자리수를 채워가는 방식의 풀이입니다.

protocol Readable {
    func readSingleValue() -> String
    func readArray(with separator: Character) -> [String]
}

extension Readable {
    func readSingleValue() -> String {
        return readLine()!
    }
    
    func readSingleValue() -> Int {
        return Int(readLine()!)!
    }
    
    func readArray(with separator: Character) -> [String] {
        return readLine()!.split(separator: " ").map { String($0) }
    }
    
    func readArray(with separator: Character) -> [Int] {
        return readLine()!.split(separator: " ").map { Int(String($0))! }
    }
}

class BOJ15649_N과M1: Readable {
    
    func input() {
        let data: [Int] = readArray(with: " ")
        n = data[0]
        array = [Int](repeating: 0, count: data[1])
        isUsed = [Bool](repeating: false, count: n+1)
    }
    
    // MARK: Properties
    
    var n: Int!
    var array: [Int]!
    var isUsed: [Bool]!
    
    // MARK: Solution
    
    func solution() {
        input()
        backTracking(digit: 0)
    }
    
    func backTracking(digit: Int) {
        guard digit < array.count else {
            print(array.reduce(into: "", { $0 += "\($1) "}))
            return
        }
        
        for i in 1...n {
            guard !isUsed[i] else { continue }
            isUsed[i] = true
            array[digit] = i
            backTracking(digit: digit+1)
            isUsed[i] = false
        }
    }
}

BOJ15649_N과M1().solution()

 

배운점

 

맞았다고 좋아하지 말고 어떻게 풀었는지, 어떻게 접근했는지를 곱씹어 보고 생각하자.