9202 Boggle

문제 링크

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

9202번: Boggle

문제 접근

백트래킹 + 이분탐색을 이용하여 해결했습니다.

 

문제를 풀기 전 Boggle이라는 게임을 어떻게 하는 건지 알아야 하기 때문에 먼저 설명해보자면

 

Boggle은 4 x 4 크기의 알파벳이 적혀있는 게임판에서 최대한 많은 단어를 찾는 게임입니다.

 

단어를 만들때는 인접한 글자(가로, 세로, 대각선 방향)를 연결해서 만들 수 있으며, 이전에 사용한 위치는 다시 사용할 수 없습니다.

 

예를 들어 Hello라는 단어가 주어지고 다음과 같은 게임판이 주어졌다고 가정해봅시다.

boggle 게임판

다음 게임판에서 Hello의 단어라는 단어를 만들려면 다음과 같이 만들 수 있습니다.

저 같은 경우 각 알파벳의 위치마다 dfs를 이용하여 백트래킹시켜 모든 경우를 탐색하도록 구현하였습니다.

 

그리고 문제에 주어지는 단어의 수가 30만개 이므로 단어를 하나하나 비교하며 같은 단어가 있는지 확인하지 않고 이분탐색으로 맞는 단어가 있는지 빠르게 탐색할 수 있도록 하였습니다.

구현

import sys
input = sys.stdin.readline

boggle = []					# 게임판이 담길 리스트
ans = [0, 0]					# 정답이 담길 리스트(최대점수, 찾은 단어 개수)
dx = [0, 0, 1, -1, 1, -1, -1, 1] 		# 인접한 주사위로 이동하기 위해 사용하는 리스트(세로)
dy = [1, -1, 1 , -1, 0, 0, 1, -1] 		# 인접한 주사위로 이동하기 위해 사용하는 리스트(가로)
score = [0, 0, 0, 1, 1, 2, 3, 5, 11] 		# 정답 점수를 저장해 놓는 리스트
visit = [[] for _ in range(4)] 			# 방문 여부를 확인하는 리스트
w = int(input()) 				# 단어의 개수를 저장하는 변수
word = [input().rstrip() for x in range(w)] 	# 입력으로 주어지는 단어를 저장
input() 					# 공백을 입력받는 용도
b = int(input()) 				# 주어지는 게임판의 수
word.sort() 					# 입력받은 단어를 이분탐색하기 위해 미리 정렬해둠
useWord = [] 					# 해당 단어를 만들었었는지 확인하는 리스트
ans_string = "" 				# 찾은 단어중 가장 긴 문자열을 확인하는 문자열 변수

def safe(x, y):
	return x >= 0 and x < 4 and y >= 0 and y < 4
    
def bst(string):
	st = 0
	ed = w - 1
	while st <= ed :
		mid = (st + ed) // 2
		if word[mid] == string:
			return mid
		elif word[mid] < string:
			st = mid + 1
		else:
			ed = mid - 1
	return -1

def dfs(x, y, tmp):
	string = "".join(tmp)
	if (len(string) >= 9) :
		return
	search = bst(string)
	if search != -1:
		global ans_string
		if len(string) > len(ans_string):
			ans_string = string
		elif len(string) == len(ans_string) and string < ans_string:
			ans_string = string
		if useWord[search] == False:
			useWord[search] = True;
			ans[1] += 1
			ans[0] += score[len(string)]
	for i in range(8):
		nx = x + dx[i]
		ny = y + dy[i]
		if safe(nx, ny) and visit[nx][ny] == False:
			visit[nx][ny] = True
			tmp.append(boggle[nx][ny])
			dfs(nx, ny, tmp)
			tmp.pop()
			visit[nx][ny] = False


for i in range(b):
	boggle = []
	for _ in range(4):
		boggle.append(input().rstrip())
	if (i < b - 1):
		input()
	ans[0] = 0
	ans_string = ""
	ans[1] = 0
	tmp = []
	for j in range(4) :
		visit[j] = [False for _ in range(4)]
	useWord = [False for _ in range(w)]
	for x in range(4):
		for y in range(4):
			tmp.append(boggle[x][y])
			visit[x][y] = True
			dfs(x, y, tmp)
			visit[x][y] = False
			tmp.pop()
	print(ans[0], ans_string, ans[1])