1167번: 트리의 지름 (acmicpc.net)


from heapq import heappop, heappush 

import sys 

input = sys.stdin.readline 


n = int(input()) 


connect = [[False for _ in range(n + 1)] for _ in range(n + 1)]


for i in range(1, n + 1, 1):

    inform = list(map(int, input().split(' ')))


    j = 1 

    while(j < len(inform)): 

        if(inform[j] == -1):

            break 


        connect[i][inform[j]] = connect[inform[j]][i] = inform[j + 1]

        j += 2 



#root node는 강제로 1로 잡자. 


max_value = 0 


visited = [False for _ in range(n + 1)] 

visited[1] = True 


def traverse(node): 

    global max_value

    values = [] #heap 


    for i in range(2, n + 1, 1): 

        if(visited[i] or not connect[node][i]): 

            continue 


        visited[i] = True 

        heappush(values, (-1) * (connect[node][i] + traverse(i)))


    if(len(values) == 0): #리프 노드인 경우 

        return 0 

    

    v1 = (-1) * heappop(values)

    v2 = 0 

    if(len(values) > 0): 

        v2 = (-1) * heappop(values) 


    max_value = max(max_value, v1 + v2) 

    return v1 


traverse(1) 

print(max_value)





1967번: 트리의 지름 (acmicpc.net)을 해결했던 코드를 주어진 문제 상황에 맞게 변형해서 제출했는데 메모리 초과가 뜨네요 ㅠㅠ 


아이디어는 각 가중치가 모두 양수니까 루트 노드를 임의로 (위 코드에서는 1번 노드) 정해주면 사실상 1967번과 상황이 똑같아진다는 것이었습니다. 


코드를 짤 때는 신경 안쓰긴 했으나 node 개수인 v의 범위가 10^6 이하이고 메모리 제한은 256MB여서 딱히 터질 거 같지는 않은데... 


역시 재귀로 코드를 짠 게 문제일까요? 스택으로 바꿔서 짜면 해결이 될지가 궁금합니다.. 





+) 그간 여러분의 도움 덕분에 현재 solved.ac 골드1 & 클래스 5까지 도달했습니다. 감사합니다!