[Python] 백준 1967 트리의 지름

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

1967번: 트리의 지름

 

# 1967 트리의 지름

N = int(input())
parents = dict() # 부모 -> 자식
childs = dict() # 자식 -> 부모
end_nums = set() # 자식이 없는 번호 모음
maxi_num = 0 # visited 만들기 위함

for _ in range(N - 1):
    parent, child, weight = map(int, input().split())
    end_nums.add(parent)
    end_nums.add(child)
    maxi_num = max(parent, child, maxi_num)

    if parent in parents:
        parents[parent].append([child, weight])
    else:
        parents[parent] = [[child, weight]]
    
    if child in childs:
        childs[child].append([parent, weight])
    else:
        childs[child] = [[parent, weight]]

# 끝 자식들부터 시작해서, 자식->부모->자식 탐색하며 maximum 값 찾기.
maximum = 0
maxi_num += 1
for num in end_nums:
    # 부모 찾기 위해 쓰는 list
    temp_num = [[num, 0]]
    # 부모 담는 임시 list
    temp_par = list()

    # 자식 -> 부모 보기
    visited = [0] * maxi_num
    visited[num] = 1
    while temp_num:
        temp, value = temp_num.pop()

        # 내가 누구의 childs면 다 추가
        if temp in childs:
            # print(f"childs[temp]: {childs[temp]}")
            for temp_child_num in childs[temp]:
                temp_num.append([temp_child_num[0], temp_child_num[1] + value])
                temp_par.append([temp_child_num[0], temp_child_num[1] + value])

        # 부모 -> 자식 보기
        while temp_par:
            temp, value = temp_par.pop()
            if visited[temp] == 1 and temp != 1:
                continue

            # 끝 숫자면 maximum 갱신
            if temp in end_nums:
                maximum = max(value, maximum)
            visited[temp] = 1

            # 내가 누구의 parents면 다 추가
            if temp in parents:
                for temp_parents_num in parents[temp]:
                    temp_par.append([temp_parents_num[0], temp_parents_num[1] + value])

print(maximum)

 

 

오랜만에 골드를 건드렸다. 좀 고생했다.

 

맨 처음 기획의도는, leaf node(자식이 없는 노드)에서 leaf node로 이동하는 최장거리를 구하려 했다.

그러나, 아마 루트 노드 ~ 리프 노드 까지의 거리를 구하는 게 정답인 예시가 있었던 것 같다. 틀렸다.

코드를 구현하는 과정에서, 난 리프 노드만 탐색한다고 생각했는데, 구현된 코드는 모든 노드를 탐색하는 것 같다.

 

생각한 핵심 아이디어를 정리하면 다음과 같다.

leaf node에서(구현된 코드는 모든 노드에서) 부모를 찾은 뒤, 부모에서 파생된 모든 자식 노드와의 거리를 비교한다.

부모의 자식 노드들과의 거리 비교가 끝나면, 부모의 부모로 올라가 모든 자식 노드와의 비교를 반복한다.

 

맨 처음 구현했을 때, 방문처리를 해주지 않아 부모 - 부모의 부모 - 부모 와 같은 경로도 탐색하여, 주어진 예시에서 49가 답으로 출력되는 현상이 있었다.

적절한 방문 처리를 통해 이 문제를 해결했다.

 

parents, childs를 구현할 때 피동 형식으로 구현한 것 같아서, 내가 풀면서도 혹은 설명하면서도 헷갈리는 순간이 있었다.

parents에 parent란 노드를 넣으면, parent의 자식이 나오고

childs에 child 노드를 넣으면, child의 부모가 나오는 방식이다.

변수명을 더 명확히 할 필요가 있다는 생각을 했다.

 

 

후기를 작성하다가 end_nums를 leaf_node로 구현하면 어떨까 생각해보고, 코드를 짰다.

leaf_node인지를 탐색하는 과정이 오래 걸려서, 시간 초과 판정을 받았다. 흑흑