글 읽기 - 런타임 에러의 원인을 찾고 싶습니다

sy6kang 3년 전 0

안녕하세요,

1967은 트리의 지름을 찾는 문제입니다. 임의의 노드에서 가장 먼 노드(x)를 찾고 거기서 가장 먼 노드를 찾아 지름을 구하는 방식을 목표로 했습니다. 문제와 질문게시판에 있는 테스트 케이스는 전부 통과하지만, 제출하면 런타임 에러가 나는 것으로 보아 제가 찾지 못한 반례가 있는 것 같습니다. 어디가 문제인지 알 수 있을까요?

import sys

n = int(sys.stdin.readline())  # node 개수
dict_n = {}  # {부모node: [[자식node: 가중치], [자식node, 가중치]]}
dict_n2 = {}  # {자식node: [[부모node: 가중치], [부모node: 가중치]]}
for i in range(n-1): # 간선 개수는 n-1개 (문제에서 주어짐)
    temp_lst = list(map(int, sys.stdin.readline().split(' ')))  # 한 줄씩 읽기
    if temp_lst[0] not in dict_n.keys():  # dict_n
        dict_n[temp_lst[0]] = [[temp_lst[1], temp_lst[2]]]
    else:
        dict_n[temp_lst[0]] = dict_n.get(temp_lst[0]) + [[temp_lst[1], temp_lst[2]]]
    if temp_lst[1] not in dict_n2.keys():  # dict_n2
        dict_n2[temp_lst[1]] = [temp_lst[0], temp_lst[2]]

# 임의의 node에서 가장 먼 node x 찾기
dist1 = [0 for _ in range(n)]  # index 주의
dist1[0] = 1  # 시작할 root node 1로 초기화

# dict와 list의 index 주의
def DFS(start, dict_n, dict_n2, dist):
    if start in dict_n.keys():  # 부모 -> 자식 방향으로 탐색
        for item in dict_n[start]:
            if dist[item[0]-1] == 0:  # 아직 안 가봤으면
                dist[item[0]-1] = dist[start-1] + item[1]
                DFS(item[0], dict_n, dict_n2, dist)  # 최대한 돌기
    if start in dict_n2.keys():  # 자식 -> 부모 방향으로 탐색
        if dist[dict_n2[start][0]-1] == 0:  # 아직 안 가봤으면
            dist[dict_n2[start][0]-1] = dist[start-1] + dict_n2[start][1]
            DFS(dict_n2[start][0], dict_n, dict_n2, dist)

DFS(1, dict_n, dict_n2, dist1)

# node x의 index
index_x = dist1.index(max(dist1))

# node x에서 가장 먼 node와의 거리 찾기
dist2 = [0 for _ in range(n)]  # index 주의
DFS(index_x+1, dict_n, dict_n2, dist2)
dist2[index_x] = 0  # node x에서 가장 먼 node를 찾는거니 node x는 제외

print(max(dist2))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

런타임 에러의 원인을 찾고 싶습니다

sy6kang 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말