Boogle 문제 링크 :https://algospot.com/judge/problem/read/BOGGLE
algospot.com :: BOGGLE
보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다. 예를 들어 그림의 (b), (c
algospot.com
프로그래밍 대회에서 배우는 알고리즘 문제해결전략 의 6장에 보면
무식하게 풀기의 예시로 Boggle 문제가 나온다.
이 문제의 정답률이 15%인 것이, 풀고싶어진 계기가 되었다.
Boggle 문제는 아래 (a) 와 같이 5x5의 글자 판이 주어지며,
각 글자 판당 N개의 단어가 주어지고 해당 글자 판에서 단어들의 존재 여부를 파악해야 하는 문제이다.
중복 탐색도 허용하나 자기 자신을 계속 참조할 수는 없다.
예를들어 (d) REPEAT의 경우 E가 두번 참조된 것을 볼 수 있다.
풀이
이 문제를 풀기 전에 개인적으로 생각했던 제약 조건은
1. try 문을 쓰지 않고 풀기
이유 : try except 문을 쓴다는 것은 에러가 발생할 상황을 프로그래머가 어느정도 알고 있다는 것인데,
그러면 그냥 그 에러가 나는 코드라인을 고치던가, 아니면 애초에 그런 에러가 안생기게 만들어야 한다.
2. flag 변수를 만들어서 다른 재귀를 종료시킬 수 있어야 한다.
이유 : BOGGLE 문제의 댓글을 보다보니, 시간초과를 내는 인풋을 보고 얻은 아이디어이다.
무식하게 푼다는 건 종료 조건 없이 모든 경우의 수를 따져보는 것인데 해당 문제의 복잡도는
O(3n )과 O(8n )의 사이라고 생각된다. 왜냐면 양 사각 테두리에서는 찾을 수 있는 경우의 수가 3가지이고,
테두리 안에 있는 대상은 8가지의 경우가 있기 때문이다.
따라서 엄청나게 복잡한 문제이며, 종료조건 없이 파이썬으로만 풀게 되면 시간 초과가 발생할 수 있다.
시간 초과가 발생할 수 있는 경우는 아래와 같다.
문제를 풀때 생각했던 아이디어
1. 각각의 좌표에서 갈 수 있는 곳이 한정되어 있음
아래 그림을 보면 꼭지점 부분에서는 서치할 수 있는 장소가 크게 3 군데만 존재한다.
반면에 꼭지점을 제외한 테두리 부분은 서치 장소가 5군데만 존재한다.
마지막으로 가운데 있는 부분은 서치 장소가 총 8 군데 존재한다.
따라서 해당 경우의 수를 계산하기 위해 서치해야 하는 해당 장소의 X,Y좌표를 받고,
그 좌표에 맞게 검색을 진행하면 된다.
2. input으로 들어오는 string을 미리 스크리닝 한다.
이유 : 들어오는 input string이 보드판에 없는 경우, 굳이 서치를 하지 않아도 되기 때문
구현
구현시의 특이점
1. global_counter를 선언하여, 모든 재귀 함수가 돌아가는 와중에 하나라도 완성본이 나온다면,
나머지를 모두 종료시켰음 이를 위해 return True 를 반환시키는 조건을 추가함.
2. result = all(elem in board_index for elem in word) 구문을 통해 단어들이 실제로 보드에 있는지 확인하였음.
TEST = int(input())
# index [x,y]
def finder(location,counter):
global word_length
global word
global global_counter
three = [[0,0],[0,4],[4,0],[4,4]]
five = [[0,1],[0,2],[0,3],[1,0],[2,0],[3,0],[4,1],[4,2],[4,3],[1,4],[2,4],[3,4]]
if global_counter:
return True
if word_length == counter:
global_counter+=1
return True
if location:
if location in three:
if location ==[0,0]:
# compare three time
if word[counter] == board[0][1]:
finder([0,1],counter+1)
if word[counter] == board[1][0]:
finder([1,0],counter+1)
if word[counter] ==board[1][1]:
finder([1,1],counter+1)
else:
return False
elif location == [0,4]:
# compare three times
if word[counter] == board[0][3]:
finder([0,3],counter+1)
if word[counter] == board[1][3]:
finder([1,3],counter+1)
if word[counter] ==board[1][4]:
finder([1,4],counter+1)
else:
return False
elif location == [4,0]:
# compare three times
if word[counter] == board[3][0]:
finder([3,0],counter+1)
if word[counter] == board[4][1]:
finder([4,1],counter+1)
if word[counter] ==board[3][1]:
finder([3,1],counter+1)
else:
return False
elif location == [4,4]:
if word[counter] == board[4][3]:
finder([4,3],counter+1)
if word[counter] == board[3][3]:
finder([3,3],counter+1)
if word[counter] ==board[3][4]:
finder([3,4],counter+1)
else:
return False
elif location in five:
if location == [0,1]:
if word[counter] == board[0][0]:
finder([0,0],counter+1)
if word[counter] == board[0][2]:
finder([0,2],counter+1)
if word[counter] ==board[1][0]:
finder([1,0],counter+1)
if word[counter] ==board[1][1]:
finder([1,1],counter+1)
if word[counter] ==board[1][2]:
finder([1,2],counter+1)
else:
return False
elif location == [0,2]:
if word[counter] == board[0][1]:
finder([0,1],counter+1)
if word[counter] == board[0][3]:
finder([0,3],counter+1)
if word[counter] ==board[1][1]:
finder([1,1],counter+1)
if word[counter] ==board[1][2]:
finder([1,2],counter+1)
if word[counter] ==board[1][3]:
finder([1,3],counter+1)
else:
return False
elif location == [0,3]:
if word[counter] == board[0][2]:
finder ([0,2],counter+1)
if word[counter] == board[0][4]:
finder ([0,4],counter+1)
if word[counter] ==board[1][2]:
finder ([1,2],counter+1)
if word[counter] ==board[1][3]:
finder ([1,3],counter+1)
if word[counter] ==board[1][4]:
finder ([1,4],counter+1)
else:
return False
elif location == [1,0]:
if word[counter] == board[0][0]:
finder([0,0],counter+1)
if word[counter] == board[0][1]:
finder([0,1],counter+1)
if word[counter] ==board[1][1]:
finder([1,1],counter+1)
if word[counter] ==board[2][0]:
finder([2,0],counter+1)
if word[counter] ==board[2][1]:
finder([2,1],counter+1)
else:
return False
elif location == [2,0]:
if word[counter] == board[1][0]:
finder([1,0],counter+1)
if word[counter] == board[1][1]:
finder([1,1],counter+1)
if word[counter] ==board[2][1]:
finder([2,1],counter+1)
if word[counter] ==board[3][0]:
finder([3,0],counter+1)
if word[counter] ==board[3][1]:
finder([3,1],counter+1)
else:
return False
elif location == [3,0]:
if word[counter] == board[2][0]:
finder([2,0],counter+1)
if word[counter] == board[2][1]:
finder([2,1],counter+1)
if word[counter] ==board[3][1]:
finder([3,1],counter+1)
if word[counter] ==board[4][0]:
finder([4,0],counter+1)
if word[counter] ==board[4][1]:
finder([4,1],counter+1)
else:
return False
elif location == [4,1]:
if word[counter] == board[4][0]:
finder([4,0],counter+1)
if word[counter] == board[4][2]:
finder([4,2],counter+1)
if word[counter] ==board[3][0]:
finder([3,0],counter+1)
if word[counter] ==board[3][1]:
finder([3,1],counter+1)
if word[counter] ==board[3][2]:
finder([3,2],counter+1)
else:
return False
elif location == [4,2]:
if word[counter] == board[4][1]:
finder([4,1],counter+1)
if word[counter] == board[4][3]:
finder([4,3],counter+1)
if word[counter] ==board[3][1]:
finder([3,1],counter+1)
if word[counter] ==board[3][2]:
finder([3,2],counter+1)
if word[counter] ==board[3][3]:
finder([3,3],counter+1)
else:
return False
elif location == [4,3]:
if word[counter] == board[4][2]:
finder([4,2],counter+1)
if word[counter] == board[4][4]:
finder([4,4],counter+1)
if word[counter] ==board[3][2]:
finder([3,2],counter+1)
if word[counter] ==board[3][3]:
finder([3,3],counter+1)
if word[counter] ==board[3][4]:
finder([3,4],counter+1)
else:
return False
elif location == [1,4]:
if word[counter] == board[0][4]:
finder([0,4],counter+1)
if word[counter] == board[0][3]:
finder([0,3],counter+1)
if word[counter] ==board[1][3]:
finder([1,3],counter+1)
if word[counter] ==board[2][3]:
finder([2,3],counter+1)
if word[counter] ==board[2][4]:
finder([2,4],counter+1)
else:
return False
elif location == [2,4]:
if word[counter] == board[1][3]:
finder([1,3],counter+1)
if word[counter] == board[1][4]:
finder([1,4],counter+1)
if word[counter] ==board[2][3]:
finder([2,3],counter+1)
if word[counter] ==board[3][3]:
finder([3,3],counter+1)
if word[counter] ==board[3][4]:
finder([3,4],counter+1)
else:
return False
elif location == [3,4]:
if word[counter] == board[2][3]:
finder([2,3],counter+1)
if word[counter] == board[2][4]:
finder([2,4],counter+1)
if word[counter] ==board[3][3]:
finder([3,3],counter+1)
if word[counter] ==board[4][3]:
finder([4,3],counter+1)
if word[counter] ==board[4][4]:
finder([4,4],counter+1)
else:
return False
else:
if word[counter] == board[location[0]-1][location[1]-1]:
finder([location[0]-1,location[1]-1],counter+1)
if word[counter] == board[location[0]-1][location[1]]:
finder([location[0]-1,location[1]],counter+1)
if word[counter] == board[location[0]-1][location[1]+1]:
finder([location[0]-1,location[1]+1],counter+1)
if word[counter] == board[location[0]][location[1]-1]:
finder([location[0],location[1]-1],counter+1)
if word[counter] == board[location[0]][location[1]+1]:
finder([location[0],location[1]+1],counter+1)
if word[counter] == board[location[0]+1][location[1]-1]:
finder([location[0]+1,location[1]-1],counter+1)
if word[counter] == board[location[0]+1][location[1]]:
finder([location[0]+1,location[1]],counter+1)
if word[counter] == board[location[0]+1][location[1]+1]:
finder([location[0]+1,location[1]+1],counter+1)
else:
return False
for _ in range(TEST):
board = []
# board maker
index = []
# getting board
for _ in range(5):
temp = input()
board.append(list(temp))
index+=list(temp)
#setting board_index to minimize check
board_index = set(index)
word_count = int(input())
for _ in range(word_count):
raw = input()
word = list(raw)
# quick index
global_counter =0
word_length = len(word)
result = all(elem in board_index for elem in word)
if result:
for x in range(5):
if not global_counter :
for y in range(5):
if not global_counter:
# first word exists
if board[x][y]==word[0]:
out1 = finder([x,y],1)
if global_counter:
print("%s YES" % raw)
break
if not global_counter:
print("%s NO" % raw)
else:
print("%s NO" % raw)
56ms면 python으로 푼 사례중 상당히 상위권에 속한다.
'Develop > Algorithm' 카테고리의 다른 글
| [Algorithm] Python3 JUMPGAME 문제 풀이 (0) | 2019.12.16 |
|---|
