[Python] 1165번 단어퍼즐

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

---

 

26/01/06

 

 

파이썬의 lzma라이브러리 사용법을 안다면 난이도에 비해 비교적 쉽게 해결할 수 있다.

---

 

문제 접근 방식:

 

 

먼저 어떻게든 단어 목록을 전처리로 하나 만들어놓는다면 단순한 백트래킹 문제가 된다.

 

당연히 단어 목록을 전부 복붙하면 바이트가 너무 커진다. 이제 전처리로 단어 목록을 "압축"하는 법을 알아보자.

 

나의 접근 방식은 다음과 같다.

 

1. 먼저 단어 리스트들을 쭉 봤다.

AARGH
AARON
ABABA
ABACK
ABANDON
ABANDONED
ABANDONING
ABANDONMENT
ABATEMENT
ABBERLEY ...

사전 순으로 정렬이 되어 있음을 확인했다.

 

2. 이 리스트를 그대로 lzma라이브러리로 압축 후, readable한 파일을 만들기 위해 압축된 바이너리 파일을 base64로 인코딩을 진행했다.

 

3. 인코딩된 문자열의 길이가 꽤나 길어서, 소스코드 제한에 걸렸다.

 

4. 소스코드 제한에 걸리지 않기 위해 base64보다 바이트 수가 더 줄어들 수 있는 base85로 인코딩을 진행했지만, 여전히 바이트 수가 커서 소스코드 길이 제한에 걸렸다.

 

4번 단계 이후로 생각을 좀 많이 했었었다. 이후 5번 단계를 생각했다. 

 

5. 기존 단어 목록이 사전 순 정렬이었기 때문에 앞 단어와 뒷 단어가 서로 Prefix가 겹치는 부분이 많았다.

 

이를 이용하여, 기존 단어 목록을 아래와 같이 변경했다.

AARGH
3ON
1BABA
3CK
3NDON
7ED
7ING
7MENT
3TEMENT
2BERLEY

3ON의 3은, 현재 단어가 이전 단어의 Prefix 3개와 겹친다는 뜻이다. 즉, 이전 단어가 AARGH였으므로 3ON은 AARON이 되는 것이다.

 

6. 해당 변경된 단어 리스트를 lzma라이브러리로 압축 후, base85로 인코딩을 진행했다. 이렇게 하니 압축된 문자열이 소스코드 길이 제한에 들어왔다.

 

7. 이후 코드에선 해당 전처리된 문자열을 압축해제했다. 그러면 Prefix가 몇개 겹치는지 수로 표현된 "변경된 단어 목록"가 나온다.

 

8. "변경된 단어 목록"를 원래 단어 목록으로 만들기 위해, 함수를 여러 개 만들었다.

 

Prefix가 몇개 겹치는지의 여부 + 접미사의 형태로 이루어져 있으므로, 이를 파싱하여 원래 단어를 복구하는 함수를 만들었다.

 

또한, 원래 단어들을 저장할 때 트라이로 저장하도록 했다.

 

9. 이후 부분은 그냥 백트래킹이다.

 

현재 노드가 현재 보고있는 위치의 문자이고, 이 문자에서 8방향으로 있는 방문하지 않은 위치의 문자를 방문하는데, 단어 목록에 존재하는 문자를 방문해야하므로 트라이 구조를 사용한 것이다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 Python 코드이다. 더보기를 누르면 확인할 수 있다.

전처리된 문자열은 길이 관계로, 삭제하여 공개한다. 문자열을 전처리하는 과정은 직접 해보자.

import base64, lzma
class Node(object):
    def __init__(self, key):
        self.key = key
        self.isEnd = False
        self.data = None
        self.children = {}
        self.parent = None
class Trie(object):
    def __init__(self):
        self.head = Node(None)
    def insert(self, string):
        now = self.head
        for char in string:
            if char not in now.children:
                now.children[char] = Node(char)
                parent = now
                now = now.children[char]
                now.parent = parent
            else:
                now = now.children[char]
        now.isEnd = True
        now.data = string
def parse(string):
    for i in range(len(string)):
        if not string[i].isdigit():
            return int(string[:i]), string[i:]
compressed = ""
original = lzma.decompress(base64.b85decode(compressed)).decode("ascii").splitlines()
trie = Trie()
beforeWord = original[0]
trie.insert(beforeWord)
for i in range(1, len(original)):
    p, suffix = parse(original[i])
    beforeWord = beforeWord[:p]+suffix
    trie.insert(beforeWord)
dr, dc = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
MAP = [input().split() for _ in range(5)]
ans = set()
vis = [[0,0,0,0,0] for _ in range(5)]
nowNode = trie.head
def dfs(r, c, nowNode):
    global ans
    if nowNode.isEnd:
        ans.add(nowNode.data)
    for i in range(8):
        nr, nc = r+dr[i], c+dc[i]
        if 0 <= nr < 5 and 0 <= nc < 5 and vis[nr][nc] == 0 and MAP[nr][nc] in nowNode.children:
            vis[nr][nc] = 1
            nowNode = nowNode.children[MAP[nr][nc]]
            dfs(nr, nc, nowNode)
            nowNode = nowNode.parent
            vis[nr][nc] = 0
    return
for r in range(5):
    for c in range(5):
        vis[r][c] = 1
        nowNode = nowNode.children[MAP[r][c]]
        dfs(r, c, nowNode)
        nowNode = nowNode.parent
        vis[r][c] = 0
print(len(ans))