[백준/Swift] 1062번: 가르침

 

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

1062번: 가르침

 

비트마스킹으로 풀어보겠습니다. 사실 이 문제는 다른 분들의 코드를 참고해서 구현했습니다. 비트마스킹을 잘 모르겠어서요^_^

wordsBit라는 배열을 사용했는데 이 부분을 2차원으로 할 수도 있지만 1차원으로도 할 수 있다! 바로, 해당 단어에 사용된 알파벳을 체크해 주는 방식인데, 시프트(shift)와 OR 연산을 사용한다!

시프트는 왼쪽 시프트 << 를 사용할 것인데, 이렇게 되면 1 << b 에서 왼쪽으로 b칸 이동하는 것이다.

즉, 1 << 2 라면 100(2) 1 << 4 라면 10000(2) 이렇게 뒤에 0의 b개수만큼 붙는다. 

그리고 OR 연산을 통해 이 들을 하나의 숫자(2진수)에 연결해주는데, 연결하고 보면 알파벳 위치가 보인다!

ex) antarctica 라면 

a -> 1 << 0   -> 1
n -> 1 << 13  -> 10000000000001
t -> 1 << 19  -> 10000010000000000001
r -> 1 << 17  -> 10100010000000000001
c -> 1 << 2   -> 10100010000000000101
i -> 1 << 8   -> 10100010000100000101

10100010000100000101
--------------------
t r   n    i     c a

-> 입력받은 단어에 있는 알파벳을 하나의 숫자(2진수)에 넣은 것이다!

wordsBit에 단어들을 변환해서 넣어주었다. 그리고 a, n, t, c, i는 무조건 포함해야 하므로 미리 alphabet에 넣어준다. (이 또한 비트마스킹으로) -> 여기서 alphabet은 배울 K개의 알파벳을 말한다.

그 후, 백트래킹을 통해 조합을 구해줬다. 

for i in start...25 {
    if (alphabet & (1 << i)) == 0 {    //해당 알파벳이 없다면! (중복제외)
        alphabet |= (1 << i)           //알파벳 추가
        backtracking(depth + 1, i)     //다음 알파벳 구하러 가기
        alphabet &= ~(1 << i)          //초기화 (알파벳 빼기)
    }
}

조합을 구하는 부분을 보면, AND(&) 연산을 통해 (1 << i) i 알파벳의 위치(a = 0, b = 1, ... z = 25 -> 뒤에서부터 시작이라는 것을 잊으면 안 된다)가 0이라면 alphabet에는 해당 알파벳이 없다는 뜻이므로 계속 진행한다. 있다면 중복이므로 패스!

그 후, 이전에 했던 것 처럼 OR연산자와 Left Shift를 통해 알파벳을 추가한다. 

if depth == k { //배울 알파벳 모두 골랐으면
    var count = 0
    for i in 0..<n { //고른 알파벳만으로 몇개의 단어를 배울 수 있는지 카운트
        if wordsBit[i] & alphabet == wordsBit[i] { //wordBit[i]의 알파벳보다 alphabet이 더 많은 알파벳을 가지고 있을 수 있으므로 둘의 공통점만 뽑아서 비교!
            count += 1
        }
    }
    answer = max(answer, count)
    return
}

만약 K개의 알파벳을 모두 골랐다면, 이제 고른 알파벳만으로 단어를 배울 수 있는지 카운팅을 해준다.

입력받은 wordsBit를 순회하면서 고른 알파벳으로 해당 단어를 배울 수 있는지 체크해야 하는데, alphabet의 개수가 wordsBit를 구성하는 알파벳의 개수보다 더 많을 수 있다. 그러므로 둘의 공통 알파벳이 wordsBit의 알파벳과 같으면 된다.

아래의 예시와 같다! 

wordsbit의 알파벳은 a, b, c, i, n, t 로 구성되어 있고 alphabet의 알파벳은 a, b, c, d, e, i, n, t 로 구성되어 있다.

둘의 공통점인 a, b, c, i, n, t가 wordsbit와 동일한데, 이는 이 wordsbit를 배울 수 있다는 것을 의미한다. 이렇게 공통점을 찾으려면 AND 연산자를 사용하면 된다. 둘 다 1인 경우만 1을 출력하기 때문~

wordsbit
10000010000100000111
alphabet
10000010000100011111
wordsbit + alphabet
10000010000100000111

 

이런 식으로 해서 모든 조합의 alphabet으로 배울 수 있는 최대 단어 개수를 구해주면 된다!

 

전체 코드

import Foundation

//input
var nk = readLine()!.split(separator: " ").map{Int(String($0))!}
var (n, k) = (nk[0], nk[1])
var answer = 0
var alphabet = 0
var wordsBit = [Int](repeating: 0, count: 51)

//문장을 입력받을 때마다 각 단어를 비트마스킹으로 추가
for i in 0..<n {
    let a = readLine()!.map{String($0)}
    for j in a {
        wordsBit[i] |= 1 << (Int(Character(j).asciiValue! - Character("a").asciiValue!))
    }
}

//조합으로 사용할 수 있는 알파벳 구하기
func backtracking(_ depth: Int, _ start: Int) {
    if depth == k { //배울 알파벳 모두 골랐으면
        var count = 0
        for i in 0..<n { //고른 알파벳만으로 몇개의 단어를 읽을 수 있는지 카운트
            if wordsBit[i] & alphabet == wordsBit[i] { //wordBit[i]의 알파벳보다 alphabet이 더 많은 알파벳을 가지고 있을 수 있으므로 둘의 공통점만 뽑아서 비교!
                count += 1
            }
        }
        answer = max(answer, count)
        return
    }

    for i in start...25 {
        if (alphabet & (1 << i)) == 0 { //해당 알파벳이 없다면! (중복제외)
            alphabet |= (1 << i)  //알파벳 추가
            backtracking(depth + 1, i)     //다음 알파벳 구하러 가기
            alphabet &= ~(1 << i) //초기화 (알파벳 빼기)
        }
    }
}

func solution() -> Int{
    if k < 5 { //a, n, t, c, i 도 못배우는 것이므로 읽을 수 있는 단어 개수가 0개!
        return 0
    }
    //비트마스킹을 사용해서 alphabet에 읽을 수 있는 단어(a, n, t, i, c) 저장
    ["a", "n", "t", "i", "c"].forEach {
        alphabet |= 1 << (Int(Character($0).asciiValue! - Character("a").asciiValue!))
    }
    k -= 5
    backtracking(0, 0)
    return answer
}

print(solution())

 

솔직히 어떻게 이렇게 구현하게 되었는지는 잘 모르겠다. 대단한 사람들... 대신 이제 어떻게 구현하는지는 알고 있으니... 이것을 바탕으로 여러 문제를 풀어보도록 해야겠다! 알파벳은 이렇게 비트 마스킹으로 해도 될 것 같다..!!