백준 11277번 2-SAT - 1 - 스위프트(Swift) 풀이

---

 

1. 변수가 최대 20개이므로, 각 변수의 값을 정하는 모든 경우의 수는 2^20이다.
2. 비트마스킹을 사용하여 모든 경우를 계산해 결과가 true가 되는 경우가 존재하는지 확인한다.

 

1. 변수가 최대 20개이므로, 각 변수의 값을 정하는 모든 경우의 수는 2^20이다.

 변수의 개수가 20개로 매우 작기 때문에 모든 경우를 고려해볼 수 있다. 각 변수마다 true/false 값 중 하나를 가지므로 모든 경우의 수는 2^20이다. 또한 각 경우의 결과값을 계산하는데 O(M)의 시간복잡도가 든다. 따라서 총 시간복잡도는 O(2^N*M).

 

2. 비트마스킹을 사용하여 모든 경우를 계산해 결과가 true가 되는 경우가 존재하는지 확인한다.

 Xi를 i번째 비트로 표현한다고 하면, 모든 변수가 false인 경우는 0, 모든 변수가 true인 경우는 (1 << N) - 1로 나타낼 수 있다. 0부터 (1 << N) - 1까지 반복문을 돌며 각 경우의 결과값을 계산해 결과값이 true가 되는 경우가 존재하는지 확인한다.

 

반응형

---

import Foundation

var N = 0, M = 0
var clauses = Array(repeating: (0,0), count: 100)

func calc(with mask: Int) -> Bool {
    var ret = true

    for m in 0..<M {
        let i = clauses[m].0
        let j = clauses[m].1
        
        var x = (mask & (1 << (abs(i)-1))) != 0
        var y = (mask & (1 << (abs(j)-1))) != 0
        
        if i < 0 { x = !x }
        if j < 0 { y = !y }
        
        ret = ret && (x || y)
    }

    return ret
}

func bruteForce() -> Int {
    for i in 0..<(1 << N) {
        if calc(with: i) { return 1 }
    }
    
    return 0
}

func solution() {
    var input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    N = input[0]
    M = input[1]
    
    for i in 0..<M {
        input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        clauses[i] = (input[0], input[1])
    }
    
    let result = bruteForce()
    print(result)
}

solution()