[BOJ/파이썬] 골드2 1167 - 트리의 지름

 💬 문제

 

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.
 

 

🔨 입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

 

 

🔨출력 

첫째 줄에 트리의 지름을 출력한다.

👊🏻 예시 입력 1 

 

5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

👊🏻 예시 출력 1

 

11

 

💡 해결

 

 트리의 지름을 구하는 방법이 따로 있는데, 그것도 알지 못한 채 호기롭게 모든 정점에서 DFS를 해주고, 그 와중에 가장 큰 값으로 계속해서 정답을 바꿔주는 로직으로 구현했다. 그런데 정점의 개수가 10^6개가 되면 2중 포문에서는 무조건 틀리게 돼있었다.

시험기간이어서.. 머리쓰다가 시간이 아까워서 어떻게 푸는지만 보기로 했다.

 

import sys
sys.setrecursionlimit(10**5)

answer = -1e7


def DFS(visited, start, sum, count):
    global answer
    global N
    answer = max(answer, sum)

    visited[start] = True

    if count == N - 1: return

    for to, weight in Graph[start]:
        if not visited[to]:
            DFS(visited, to,sum + weight, count + 1)


N = int(input())
Graph = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
    tmp = list(map(int, sys.stdin.readline().split()))
    for j in range(1, len(tmp) - 1, 2):
        Graph[i].append([tmp[j], tmp[j + 1]])

for i in range(1, N + 1):
    visited = [False] * (N + 1)
    DFS(visited, i, 0, 0)

print(answer)


answer = -1e7


def DFS(visited, start, sum, count):
    global answer
    global N
    answer = max(answer, sum)

    visited[start] = True

    if count == N - 1: return

    for to, weight in Graph[start]:
        if not visited[to]:
            DFS(visited, to,sum + weight, count + 1)


N = int(input())
Graph = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
    tmp = list(map(int, sys.stdin.readline().split()))
    for j in range(1, len(tmp) - 1, 2):
        Graph[i].append([tmp[j], tmp[j + 1]])

for i in range(1, N + 1):
    visited = [False] * (N + 1)
    DFS(visited, i, 0, 0)

print(answer)

원래 코드입니당..^^

 

 

방법은 간단했다.

1. 아무정점에서나 탐색을 하여 가장 멀리 있는 정점을 구한다.

2. 그 정점에서 탐색을 하여 가장 멀리 있는 정점과의 길이를 구한다.

왜 그렇지 하고 생각을 좀..해보니 이진트리에서 아무 정점이나 잡아놓고 가장 먼 점을 구하면 가장 양 끝단의 점 중 반대편에 위치한 곳으로 갈 것이다. 그렇다면 거기서 가장 먼 점을 탐색하면 반대편 가지 중 가장 밑에 있는 정점을 구하게 될것이다.

 

솔직히 말해 이런건 코테나오면 무조건 시간초과 각오를 해야겠다. 이런 발상을 긴장된 와중에 발현하기란 쉽지 않을 것 같다.

내 구현력이 늘었다는 것에 만족하고 떠납니다.

👨🏻‍💻  CODE
 

import sys

sys.setrecursionlimit(10 ** 7)

start = 0
flag = 0


def DFS(x, wei):
    for i in Graph[x]:
        a, b = i
        if visited[a] == -1:
            visited[a] = wei + b
            DFS(a, wei + b)


N = int(input())
Graph = [[] for _ in range(N + 1)]
for _ in range(N):
    line = list(map(int, input().split()))
    cnt_node = line[0]
    idx = 1
    while line[idx] != -1:
        adj_node, adj_cost = line[idx], line[idx+1]
        Graph[cnt_node].append((adj_node, adj_cost))
        idx += 2


visited = [-1] * (N + 1)
visited[1] = 0
DFS(1,0)

start = visited.index(max(visited))
visited = [-1] * (N + 1)
visited[start]=0
DFS(start,0)

print(max(visited))

 

 

💪🏻 결과

 

ㅋㅋ