[BOJ_Platinum 5] 9202 - Boggle [python]

9202번: Boggle (acmicpc.net)

9202번: Boggle

 

입력

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

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

출력

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

 

Trie를 이용한 문제입니다.

기본적인 Trie에, DFS를 접목해 풀이하는 것이 가능합니다.

 

먼저 이전에 풀었던 Trie문제들과 같이, 각각의 단어들을 바탕으로 Trie를 생성합니다.

이후, Boggle의 4 x 4 크기의 칸을 DFS로 돌아다니며, 주어진 단어중 만드는 것을 Set에 추가합니다.

DFS 진행 시 유망하지 않은, 즉 현재까지의 문자열을 부분으로 하는 단어가 없는 경우 탐색을 진행하지 않고 return함에 유의합니다.

 

 

import sys

input = sys.stdin.readline

class TrieNode():
    def __init__(self):
        self.fin = False
        self.child = dict()

    def add(self,string):
        cur = self

        for s in string:
            if s not in cur.child:
                cur.child[s] = TrieNode()
            cur = cur.child[s]
        cur.fin = True

visit = [[False for i in range(4)] for i in range(4)]
dx,dy = [0,1,0,-1,1,-1,1,-1],[1,0,-1,0,1,-1,-1,1]

def dfs(x,y,string,cur):
    #글자의 마지막이면서, 아직 resultSet에 들어있지 않은 경우 추가
    if cur.fin and string not in resultSet:   
        resultSet.add(string)
    
    #주어진 단어 중 최대 단어의 길이를 넘은 경우 탐색할 이유가 없음
    if len(string) >= maxLen: return

    visit[x][y] = True
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        
        #유망한 경우에만 탐색을 진행함
        if 0 <= nx < 4 and 0 <= ny < 4 and not visit[nx][ny] and boggle[nx][ny] in cur.child:
            dfs(nx,ny,string+boggle[nx][ny],cur.child[boggle[nx][ny]])

    visit[x][y] = False

maxLen = 0
scoreList = [0,0,0,1,1,2,3,5,11]
Trie = TrieNode()
for i in range(int(input())):
    string = input().rstrip()
    maxLen = max(len(string),maxLen)
    Trie.add(string)

input()

for i in range(int(input())):
    if i: input()

    boggle = [list(input().rstrip()) for _ in range(4)]
    resultSet = set()

    for x in range(4):
        for y in range(4):
            if boggle[x][y] in Trie.child:
                dfs(x,y,boggle[x][y],Trie.child[boggle[x][y]])
    score = 0
    target = False
    for string in resultSet:
        score += scoreList[len(string)]
        if not target or len(target) < len(string) or (len(target) == len(string) and target > string):
            target = string

    print(score,target,len(resultSet))

import sys

input = sys.stdin.readline

class TrieNode():
    def __init__(self):
        self.fin = False
        self.child = dict()

    def add(self,string):
        cur = self

        for s in string:
            if s not in cur.child:
                cur.child[s] = TrieNode()
            cur = cur.child[s]
        cur.fin = True

visit = [[False for i in range(4)] for i in range(4)]
dx,dy = [0,1,0,-1,1,-1,1,-1],[1,0,-1,0,1,-1,-1,1]

def dfs(x,y,string,cur):
    #글자의 마지막이면서, 아직 resultSet에 들어있지 않은 경우 추가
    if cur.fin and string not in resultSet:   
        resultSet.add(string)
    
    #주어진 단어 중 최대 단어의 길이를 넘은 경우 탐색할 이유가 없음
    if len(string) >= maxLen: return

    visit[x][y] = True
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        
        #유망한 경우에만 탐색을 진행함
        if 0 <= nx < 4 and 0 <= ny < 4 and not visit[nx][ny] and boggle[nx][ny] in cur.child:
            dfs(nx,ny,string+boggle[nx][ny],cur.child[boggle[nx][ny]])

    visit[x][y] = False

maxLen = 0
scoreList = [0,0,0,1,1,2,3,5,11]
Trie = TrieNode()
for i in range(int(input())):
    string = input().rstrip()
    maxLen = max(len(string),maxLen)
    Trie.add(string)

input()

for i in range(int(input())):
    if i: input()

    boggle = [list(input().rstrip()) for _ in range(4)]
    resultSet = set()

    for x in range(4):
        for y in range(4):
            if boggle[x][y] in Trie.child:
                dfs(x,y,boggle[x][y],Trie.child[boggle[x][y]])
    score = 0
    target = False
    for string in resultSet:
        score += scoreList[len(string)]
        if not target or len(target) < len(string) or (len(target) == len(string) and target > string):
            target = string

    print(score,target,len(resultSet))