9202번: Boggle

문제 출처 : https://www.acmicpc.net/problem/9202

9202번: Boggle

언어 : Kotlin

 

문제 설명 :

상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 

상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다.

Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다.

1글자, 2글자로 이루어진 단어는 0점, 3글자, 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점이다. 점수는 자신이 찾은 단어에 해당하는 점수의 총 합이다.

단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다.

그 다음에는 Boggle 보드의 개수 b가 주어진다. (1 < b < 30) 모든 Boggle은 알파벳 대문자로 이루어져 있고, 4줄에 걸쳐 주어진다. 각 Boggle의 사이에는 빈 줄이 하나  있다.

 

출력 :

각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다. 각 Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다.

 

제한 사항 :

• 시간 제한 : 10초
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
5 ICPC ACM CONTEST GCPC PROGRAMM 3 ACMA APCA TOGI NEST PCMM RXAI ORCN GPCG ICPC GCPC ICPC GCPC	8 CONTEST 4 14 PROGRAMM 4 2 GCPC 2

 

풀이 : 

Trie와 DFS를 사용한 문제

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter


val trie = Trie()
lateinit var board: Array<CharArray>
lateinit var visited: Array<BooleanArray>
val dx = intArrayOf(0, 0, -1, 1, 1, 1, -1, -1)
val dy = intArrayOf(-1, 1, 0, 0, 1, -1, 1, -1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val w = readLine().toInt()
    repeat(w) {
        trie.insert(readLine())
    }
    readLine()

    val b = readLine().toInt()
    repeat(b) {
        board = Array(4) { CharArray(4) }
        visited = Array(4) { BooleanArray(4) }

        for (i in 0 until 4) {
            readLine().forEachIndexed { j, c ->
                board[i][j] = c
            }
        }

        val strSet = HashSet<String>()
        for (y in 0 until 4) {
            for (x in 0 until 4) {
                visited[y][x] = true
                dfs(x, y, board[y][x] + "", strSet)
                visited[y][x] = false
            }
        }

        printResult(strSet, bw)

        if (it < b) readLine()
    }

    bw.close()
}

fun printResult(strSet: HashSet<String>, bw: BufferedWriter) {
    val list = ArrayList<String>(strSet).sorted()
    var score = 0

    for (i in list) {
        score += getScore(i.length)
    }

    bw.appendLine("$score ${list.maxBy { it.length }} ${list.size}")
    bw.flush()
}

fun getScore(length: Int): Int {
    var score = 0
    score += when (length) {
        3, 4 -> 1
        5 -> 2
        6 -> 3
        7 -> 5
        8 -> 11
        else -> 0
    }

    return score
}

fun dfs(x: Int, y: Int, str: String, strSet: HashSet<String>) {
    if (trie.find(str, true)) strSet.add(str)

    for (i in 0 until 8) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue
        if (visited[ny][nx]) continue

        val key = str + board[ny][nx]
        if (trie.find(key, false)) {
            visited[ny][nx] = true
            dfs(nx, ny, key, strSet)
            visited[ny][nx] = false
        }
    }
}

class Trie(private val root: TrieNode = TrieNode()) {
    fun insert(key: String) {
        val length = key.length
        var cur = root

        for (i in 0 until length) {
            val next = key[i] - 'A'
            if (cur.child[next] == null) {
                cur.child[next] = TrieNode()
                cur.nodeChild++
            }

            cur = cur.child[next]!!
        }

        cur.isFinish = true
    }

    fun find(key: String, isCompleteString: Boolean): Boolean {
        val length = key.length
        var cur = root

        for (i in 0 until length) {
            val next = key[i] - 'A'
            if (cur.child[next] == null) return false
            cur = cur.child[next]!!
        }

        return if (isCompleteString) cur.isFinish else true
    }
}

class TrieNode {
    val child = arrayOfNulls<TrieNode>(26)
    var isFinish = false
    var nodeChild = 0
}