소프티어

파이썬으로 TC 4번이 아무리 해도 통과가 안되는 것 같아요...

자바로는 특별히 branching 하지 않아도 모든 테스트 케이스가 통과하는데 파이썬이 통과가 안되요 ㅜㅜ

4번 테케만 실패하는 파이썬 코드

from collections import deque
import sys

N, M = map(int, sys.stdin.readline().split())
S = sys.stdin.readline()

answer = 0

graphs = [[] for _ in range(N+1)]
for _ in range(N-1):
    a = sys.stdin.readline().split()
    start, end, spell = int(a[0]), int(a[1]), a[2]
    graphs[start].append((end, spell))
    graphs[end].append((start, spell))


### 리프 노드 찾기 ###
leaf_nodes = set()
for i in range(1, N+1):
    if i == 1:
        continue
        
    if len(graphs[i]) == 1:
        leaf_nodes.add(i)

######문자열 탐색#######
# (정점, 현재 문자열) 형태로 q에 담음
q = deque()
q.append((1, ""))
visited = [0] * (N+1)
visited[1] = 1
strings = set()
flag = False
while q:
    top = q.popleft()
    now, spells = top[0], top[1]

    if now in leaf_nodes:
        strings.add(spells)
        if spells == S:
            answer = len(S)
            flag = True
            break
        continue

    for neighbor in graphs[now]:
        next_vertex, alpha = neighbor[0], neighbor[1]
        if visited[next_vertex] == 0:
            visited[next_vertex] = 1
            q.append((next_vertex, spells + alpha))

## LCS 찾기 ##
if flag:
    print(answer)

else:
    strings = list(strings)
    strings.sort(key = lambda x : -len(x))
    
    for words in strings:
        h, w = M, len(words)
        if w <= answer:
            continue
        
        cache = [[0] * (w+1) for _ in range(h+1)]
        
        for i in range(1, h+1):
            for j in range(1, w+1):
                if S[i-1] == words[j-1]:
                    cache[i][j] = cache[i-1][j-1] + 1
                else:
                    cache[i][j] = max(cache[i][j-1], cache[i-1][j])
    
        answer = max(answer, cache[-1][-1])
    
    print(answer)