#1062 가르침

문제

---

 

코드

---

package part2

fun main() = with(System.`in`.bufferedReader()) {
    val fix = mutableSetOf('a', 'n', 't', 'i', 'c')
    val (n, k) = readLine().split(' ').map { it.toInt() }
    val words = mutableListOf<Int>() // 제공된 단어 리스트
    val alphabet = BooleanArray(26) // 필요한 알파벳 체크(visited 역할)
    var max = 0

    repeat(n) {
        val w = readLine().toCharArray().toSet().minus(fix) // 집합으로 변경 후 항상 필요한 알파벳 제외
        var bitSet = 0
        for (e in w) {
            val bitPos = e - 'a'
            bitSet = bitSet or (1 shl bitPos) // 필요한 알파벳을 비트로 저장
            alphabet[bitPos] = true
        }
        words.add(bitSet)
    }

    fun dfs(start: Int, count: Int, toLearn: Int) {
        if (count == k - 5) {
            var canLearn = 0
            for (word in words) {
                if (word and toLearn == word) canLearn++ // and 연산으로 특정 알파벳이 포함되어있는지 확인
            }
            if (canLearn > max) max = canLearn
            return
        }
        for (i in start..<alphabet.size) { // start 인덱스 이전에는 이미 확인했으니까 그 이후만 확인
            if (!alphabet[i]) continue
            alphabet[i] = false
            dfs(i, count + 1, toLearn or (1 shl i)) // or 연산으로 다른 알파벳 추가
            alphabet[i] = true
        }
    }

    if (k < 5) println(0)
    else if (alphabet.filter { it }.size <= k - 5) println(n)
    else {
        dfs(0, 0, 0)
        println(max)
    }
}

 

풀이

---

문제를 봤을 때 집합을 쓰면 되겠다고 생각했다.

항상 단어의 시작과 끝은 anta, tica이기 때문에, a, n, t, i, c는 항상 포함되어야 한다.

그렇게 되면 k개의 알파벳 중에 5개를 제외한 k-5개의 알파벳을 더 배울 수 있게 된다.

알파벳 26개 중에 k-5개를 선택하는 문제인데, 단어를 가장 많이 배울 수 있어야 하기 때문에 주어진 단어에서 사용된 알파벳만 확인하도록 한다.

알파벳 하나하나 개수를 세면서 가장 많이 사용된 알파벳을 선택하는 그리디적 알고리즘으로는 반례가 존재한다.

예를 들어 antarrrrtica, antabtica, antabcatica 이런 식으로 알파벳이 주어졌을 때

a, n, t, i, c를 제외하고 r이 가장 많이 사용되었지만 b를 선택하는게 더 많은 단어를 배울 수 있다.

따라서 완전 탐색이 필요했다.

 

이전과 같이 백트래킹으로 풀면 편할 것 같아서 백트래킹으로 구현했다.

처음에 구현한 코드는 아래와 같다.

// 시간 초과 코드
import java.util.Stack

fun main() = with(System.`in`.bufferedReader()) {
    val fix = mutableSetOf('a', 'n', 't', 'i', 'c')
    val (n, k) = readLine().split(' ').map { it.toInt() }
    val words = mutableListOf<Set<Char>>() // fix를 제외하고 나머지 알파벳들을 저장할 리스트
    val alphabet = BooleanArray(26) // 알파벳이 사용되었는지 확인하는 용도로 visited의 개념으로 사용
    val s = Stack<Char>() // 완전 탐색을 위한 스택으로 지금까지 선택된 알파벳들을 저장
    var max = 0

    repeat(n) {
        val w = readLine().toCharArray().toSet().minus(fix) // a, n, t, i, c 제외한 알파벳 저장
        for (e in w) {
            alphabet[(e - 97).code] = true // 아스키 코드를 이용해서 알파벳 사용 여부 저장
        }
        words.add(w)
    }

    fun dfs(count: Int) {
        if (count == k - 5) { // k-5개의 알파벳을 선택하면 max값을 비교한 후 종료 (a, n, t, i, c는 고정적으로 배움)
            var canLearn = 0
            for (e in words) {
                if (e.size > k - 5) continue // 배울 수 있는 k-5개의 알파벳보다 많은 알파벳이 사용된 경우 배울 수 없는 단어
                if (s.containsAll(e)) canLearn++ // 현재까지 선택한 알파벳 집합으로 해당 단어를 배울 수 있음
            }
            if (canLearn > max) max = canLearn // max 값 갱신
            return
        }
        for (i in alphabet.indices) { // 알파벳 a ~ z까지
            if (alphabet[i]) { // 만약 사용되지 않은 알파벳이면 확인하지 않음 추가해봤자 아무 단어도 배울 수 없기 때문
                s.add((i + 97).toChar())
                alphabet[i] = false
                dfs(count + 1)
                s.pop()
                alphabet[i] = true
            }
        }
    }

    dfs(0)
    println(max)
}

 

이렇게 제출했을 땐 시간 초과가 발생했다.

 

처음에 시간 초과가 떴을 땐 dfs의 스택 문제인가 싶었다.

그래서 dfs 인자를 이용해서 메모리를 더 적게 쓰면서 효율적으로 코드를 구현할 수 있는 방법을 생각했다.

 

완전 탐색에 대해 찾아보다가 좋은 블로그를 발견했다.

https://hongjw1938.tistory.com/78

알고리즘 - 완전탐색(Exhaustive Search)

여기서 비트마스킹에 대해 알게되었다.

and, or 과 같은 연산은 알았지만, 집합을 나타내고 집합과 관련된 내용이 적혀있었다.

읽다 보니, 이 문제에도 적용할 수 있을 것 같았다.

 

내가 비트연산을 이용해서 구현할 수 있는 부분은 아래와 같다.

1. 집합 포함 여부 검사
2. 스택 대신 선택한 알파벳을 저장

 

우선 집합을 비트로 표현하는 방법에 대해 알아보자

예를 들어 'acd' 라는 단어를 비트로 표현하면 1101 다.

a가 0번째 비트, b가 1번째 비트 이런 식이다.

즉, 가장 오른쪽부터 a b c d ... 를 나타내는 것이다. 

 

이렇게 표현하면 숫자를 가지고 집합을 표현할 수 있다.

다시 말하면 acd를 13(1 + 4 + 8) 이라는 숫자로 표현할 수 있는 것이다.

 

Set<Char>형 리스트를 사용하는 것보다 적은 메모리를 차지하게 된다.

 

 

1. 집합 포함 여부 검사

집합에 특정 알파벳이 포함되는지 확인하기 위해서는 and 연산을 이용한다.

and연산은 두 비트가 1이어야 1이 된다.

따라서 확인하고자 하는 특정 알파벳들의 비트 위치를 1로 두고 나머지는 0으로 둔다.

acd라는 집합에 a가 포함되어있는지 확인

1101 and 0001 = 0001 (a 포함)

acd라는 집합에 b가 포함되어있는지 확인

1101 and 0010 = 0000 (b 미포함)

 

코드에선 이런 식으로 사용했다.

if (count == k - 5) {
    var canLearn = 0
    for (e in words) {
        if (e and toLearn == e) canLearn++
    }
    if (canLearn > max) max = canLearn
    return
}

 

현재까지 선택한 알파벳 집합을 비트로 표현한 toLearn과 n개의 단어들을 각각 and연산해서 

지금 까지 선택한 알파벳 집합으로 몇 개의 단어를 배울 수 있는지 확인하는 코드이다.

max 값을 갱신하기 위해서 계산한다.

 

 

2. 선택한 알파벳을 저장

집합에 해당 알파벳을 저장하기 위해 or 연산과 시프트 연산을 사용한다.

or 연산은 집합에 추가하는 용도고, 시프트 연산은 알파벳을 비트로 나타내는 용도다

 

여기서 잠깐 시프트 연산에 대해서 설명하자면
왼쪽 시프트 연산은 왼쪽으로 비트를 k번 옮긴다는 의미다.
1 << 5 는 비트를 왼쪽으로 5번 옮겨서 10000이 되는데, 이 값은 1 * 2^5 의 결과와 같다.
즉, n << k 는 n * 2^k 와 같은 의미다.

반대로 오른쪽 시프트 연산은 오른쪽으로 비트를 k번 옮긴다는 의미다.
 30 >> 3 는 11110 비트를 오른쪽으로 3번 옮기는 것이다.
오른쪽으로 옮겨진 비트는 버려지게 된다.
따라서 11만 남게 되는데 결과는 3이 되고, 이 값은 30 / 2^3 의 결과와 같다.
즉, n >> k 는 n / 2^k 와 같은 의미다.

 

따라서 e라는 알파벳을 집합에 포함시키고 싶으면

e는 5번째 알파벳으로 1을 왼쪽으로 5비트 옮겨서 표현할 수 있다.

코틀린에서 왼쪽 시프트 연산자는 shl 키워드를 사용하면 된다.

 

코드에서는 이런 식으로 사용했다.

var bitSet = 0
for (e in w) { // 주어진 단어에서 a, n, t, i, c를 제외한 알파벳 집합이 w
    val bitPos = e - 'a'
    bitSet = bitSet or (1 shl bitPos)
    alphabet[bitPos] = true
}

비트 위치를 찾기 위해 'a'를 빼줘서 a를 0 위치로 만든다.

'a'는 아스키코드로 97을 의미하기 때문에 97을 빼준다고 생각하면 된다

이렇게 하면 a는 0, b는 1, c 는 2 ... 이 된다.

 bitSet은 집합을 비트로 표현한 것이고, 위에서 설명한대로 시프트 연산을 이용해서 알파벳 하나하나 bitSet에 추가시켜준다.

 

실제 bitSet은 이런 식으로 저장된다.

실제 bitSet

실제로는 숫자로 저장되고, 비트로 표현하면 아래 줄과 같이 표현된다.

 

---

비트 연산을 사용하면 시간을 매우 단축할 수 있다.

그래서 비트 연산을 사용했음에도 시간 초과가 발생했다...

 

질문 게시판에서 반례를 찾아보다가 발견한 문제점들이 있었다.

우선, 배울 수 있는 알파벳 개수 k가 주어진 단어들에서 사용된 알파벳 개수보다 많은 경우는 굳이 dfs로 확인할 필요가 없다는 것이다.

이 경우 그냥 모든 단어를 배울 수 있기 때문에 그냥 n을 출력하면 된다.

이와 반대로 고정 5개의 알파벳은 배워야 단어를 배울 수 있는데, k가 5보다 작게 되면 모든 단어는 배울 수 없게 된다.

이 경우엔 그냥 0을 출력하면 된다.

 

이렇게만 해도 필요없는 dfs의 호출을 꽤나 막을 수 있다.

이렇게 했는데도 n = 50, k = 15의 케이스가 동작하지 않았다.

여기서 더 이상 뭘 더 줄여야 할 지 도저히 모르겠어서 구글링을 했다.

 

https://ongveloper.tistory.com/132

백준 1062 가르침 c++, Kotlin (문자열,조합/DFS)

이 블로그를 보고 있는데, dfs의 인자로 인덱스를 넘겨주는 것이다...

 

앞에있는 알파벳은 이미 확인했고, 중복도 허용되지 않기 때문에, 굳이 알파벳 26개를 전부 탐색하지 않아도 되는 것이었다..

나도 그래서 dfs의 인자로 인덱스를 추가하고, for문을 index부터 끝까지로 변경하니까 해결됐다..

 

dfs문제는 시간초과가 많이 걸린다는게 문제인것 같다.

효율적인 알고리즘을 위해선 확실한 종료조건과 쓸데없는 재귀함수의 호출을 막아야 한다는 것을 다시 한번 느꼈다..

성공 코드는 문제 바로 아래의 코드를 확인해주세요