백준[19585] 전설 (Python3)

TLE 해결법을 몰라서 풀이 살짝 본 문제
딕셔너리 키값이 아스키 문자 하나인 경우, 숫자로 바꿔주는 게 TLE 받을 일이 적어질 거란 것을 알았다.

시간 초과 - 재귀 풀이

색상 이름이 aa, aaa인 경우 비교 과정에서
aa에서 색상 이름 비교를 중단하고 닉네임을 비교할지, 색상을 마저 비교할지에 대해 분기를 태워야 한다 생각했다.
80%대에서 TEL를 받았다.

문자열 뒤집기

다른 사람들 풀이 보고 적용한 풀이
색상 같은 경우 그냥 앞에서 비교하면 되지만, 닉네임 같은 경우 어디부터 시작할지를 모른다.
하지만 확실한 것은 수상할 팀명의 마지막은 무조건 닉네임이 들어간다.

따라서 닉네임을 입력받을 때, 뒤집어서 입력받고
비교하는 부분도 팀명을 뒤집어서 비교한다.

 

이 과정에서 문자열의 끝을 의미하는 토큰을 만난다면(여기선 -1로 함)
해당 인덱스의 카운팅을 1 올려준다.

탐색이 끝난 후 카운팅이 2인 배열이 있다면, 그 팀은 색상 이름과 닉네임이 이어진 형태이다.

어떤 문제들은 거꾸로 푸는 게 더 효율적일 수 있단 것을 알고 있었는데
왜 이 생각을 못했는지 모르겠다..

 

class Trie:
    def __init__(self):
        self.root = {}
        self.dir = [[1, 0], [1, 1], [1, -1], [-1, 0], [-1, 1], [-1, -1], [0, 1], [0, -1]]
        self.score = [0, 0, 0, 1, 1, 2, 3, 5, 11]
        self.board = []
        self.visit = [[False for _ in range(4)] for _ in range(4)]
        self.total = 0
        self.find_sentence = ""
        self.found = set()

    def insert(self, S):
        current_node = self.root
        for s in S:
            if s not in current_node:
                current_node[s] = {}
            current_node = current_node[s]
        current_node[0] = True

    def search(self, here_y, here_x, here_s, here_node):
        if 0 in here_node:
            S = "".join(here_s)
            if S not in self.found:
                self.found.add(S)
                self.total += self.score[len(S)]
            self.find_sentence = S
        for d in self.dir:
            there_y, there_x = here_y + d[0], here_x + d[1]
            if there_y < 0 or there_y >= 4 or there_x < 0 or there_x >= 4:
                continue
            if self.visit[there_y][there_x]:
                continue
            s = self.board[there_y][there_x]
            if s not in here_node:
                continue
            self.visit[there_y][there_x] = True
            self.search(there_y, there_x, here_s + [s], here_node[s])
            self.visit[there_y][there_x] = False

    def getSentence(self):
        max_len, max_sentence = 0, ""
        temp = list(self.found)
        temp = sorted(temp, key=lambda x: (len, x))
        for sentence in temp:
            if max_len < len(sentence):
                max_len = len(sentence)
                max_sentence = sentence
        return max_sentence


def main():
    N = int(input())
    trie, words = Trie(), []
    for _ in range(N):
        trie.insert(input())
    input()  # 다음 공백 줄 제거용
    T = int(input())
    for t in range(T):
        trie.board = []
        trie.total = 0
        trie.find_sentence = ""
        trie.found = set()
        for i in range(4):
            trie.board.append(input())
        if t < T - 1:
            input()  # 다음 공백 줄 제거용
        for i in range(4):
            for j in range(4):
                s = trie.board[i][j]
                if s not in trie.root:
                    continue
                trie.visit[i][j] = True
                trie.search(i, j, [s], trie.root[s])
                trie.visit[i][j] = False
        print(trie.total, trie.getSentence(), len(trie.found))


if __name__ == "__main__":
    main()