import sys; input = lambda: sys.stdin.readline().strip()
dr = (1,0),(0,1),(-1,0),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)
score_count = [0,0,0,1,1,2,3,5,11]
def insert(word):
now = trie
for char in word:
now = now.setdefault(char, dict())
# 문자열이 끝이나면 0에 전체 단어를 담아 둔다.
now[0] = word
# i,j : 2차원 배열의 인덱스, now: 현재 trie위치, visit: 방문 표시(비트마스킹)
def backtrack(i,j,now,visit):
# 0이 있다 => 어떤 한 문자열이 완성되었다. => answer에 추가
if 0 in now:
answer.add(now[0])
# 8방향으로 순회하면서
for di,dj in dr:
x,y = i+di, j+dj
if 0<=x<4 and 0<=y<4:
# 방문 확인
if visit & 1 << x*4+y: continue
# 가려는 방향의 철자가 현재 깊이의 trie에 존재하는 경우, 백트래킹을 계속 진행한다.
if arr[x][y] in now:
nxt = now[arr[x][y]]
backtrack(x,y, nxt, visit | 1 <<x*4+y)
# trie로 사용할 딕셔너리를 할당한다.
trie = dict()
# 입력을 trie 방식으로 저장한다.
words = [input() for _ in range(int(input()))]
for word in words:
insert(word)
input()
for _ in range(int(input()):
arr = [list(input()) for _ in range(4)]
answer = set()
# 4*4 배열을 순회하면서
for i in range(4):
for j in range(4):
# trie에 저장된 값이라면
if arr[i][j] in trie:
# 해당 값 내부로 들어가서 백트래킹을 수행한다.
now = trie[arr[i][j]]
visit = 1 << i*4 + j
backtrack(i,j, now, visit)
# 점수 계산
score = 0
cnt = len(answer)
max_text = ""
# answer 배열을 순회하면서,
for ans in answer:
# 각 문자열에 해당 하는 점수를 더하고
score += score_count[len(ans)]
# 가장 긴 문자열을 찾는다
if len(ans) > len(max_text):
max_text = ans
elif len(ans) == len(max_text):
max_text = min(ans, max_text)
# 출력
print(score, max_text, cnt)
input()
트라이
문자 검색을 효율적으로 구현하기 위해 트라이를 활용했습니다.
이를 별도의 클래스 구현 없이 딕셔너리만 활용했습니다.
문자열의 끝을 0으로 두어 0이 있는 경우 문자열의 끝이고, 여기에 전체 문자열을 저장해 백트래킹 시 별도의 저장이 필요 없도록 설계했습니다.
백트래킹
퍼즐 내에 있는 단어를 찾아가는 내용이기 때문에, 백트래킹을 통해 현재 위치에서 탐색을 통해 갈 수 있는 곳과, 지금까지 탐색을 진행한 trie의 위치를 저장하고, 현재 위치가 문자열의 끝인 경우 answer에 담습니다.
비트마스킹
퍼즐 내에서 중복된 블록은 사용이 불가능하기 때문에, 방문 처리가 필요합니다.
4*4의 배열을 사용하기 때문에 비트마스킹으로 구현하면 범위 내에서 방문처리가 가능하기 때문에 visit 배열을 구성하는 것보다 공간적으로 더욱 효율적인 구현이 가능합니다.
동현