[백준 파이썬] 1167 트리의 지름

1167번: 트리의 지름

문제

 

 

트리의 정보가 주어지고 트리의 지름을 구하는 문제이다.

---

아이디어

트리의 지름은 가장 먼 거리의 두 정점 사이의 거리이다. 따라서 가장 멀리 떨어져 있는 두 정점을 구한 후 거리를 계산하면 된다.

가장 먼 거리에 있는 두 정점을 얻는 방법은 떠올리지 못해 구글링을 통하여 방법을 알아내었다.

방법은 다음과 같다.

1. 임의의 정점에서 가장 먼 거리에 있는 정점을 구한다.

2. 구한 정점에서 또 다시 가장 먼 거리에 있는 정점을 구한다.

3. 두 정점 사이의 거리가 가장 먼 거리가 된다.

 

결국 가장 먼 거리를 2번 구하면 된다. 따라서 DFS를 2번 사용하면 된다고 생각했다.

---

풀이

트리의 정보를 받기 위해 입력받는 코드를 작성하였다.

V = int(input())

tree = [[] for _ in range(V + 1)]

for _ in range(V):
    data = list(map(int, input().split()))
    firstNode = data[0]

    for i in range(1, len(data)-1, 2):
        secondNode, secondDist = data[i], data[i + 1]
        tree[firstNode].append((secondNode, secondDist))

 

DFS를 사용하기 위해 방문 정보를 알 수 있는 visited배열을 생성하였다. 이 때 visited에 거리 정보도 넣기 위해 visited[1]을 0으로 초기화 시켜주었다.

visited = [-1] * (V + 1)
visited[1] = 0

 

이후 DFS를 구현하였다.

def DFS(node, dist):
    for v, d in tree[node]:
        calDist = dist + d
        if visited[v] == -1:
            visited[v] = calDist
            DFS(v, calDist)
    return

 

가장 먼저 1번 정점과 자신의 거리(0)을 DFS에 넣는다. 그럼 visited에 정점들의 거리가 입력되어 그걸 이용해 가장 먼 거리의 정점과 정보를 tmp에 넣는다. 

그 뒤 visited를 다시 -1로 초기화하고 가장 먼 정점의 visited를 0으로 초기화하여 DFS를 한번 더 사용한다.

최종적으로 얻어진 visited의 최대값을 출력하면 출력값은 트리의 지름이 된다.

 

DFS(1, 0)
tmp = [0, 0]

for i in range(1, len(visited)):
    if visited[i] > tmp[1]:
        tmp[1] = visited[i]
        tmp[0] = i

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

 

---

코드

V = int(input())

tree = [[] for _ in range(V + 1)]

for _ in range(V):
    data = list(map(int, input().split()))
    firstNode = data[0]

    for i in range(1, len(data)-1, 2):
        secondNode, secondDist = data[i], data[i + 1]
        tree[firstNode].append((secondNode, secondDist))


visited = [-1] * (V + 1)
visited[1] = 0


def DFS(node, dist):
    for v, d in tree[node]:
        calDist = dist + d
        if visited[v] == -1:
            visited[v] = calDist
            DFS(v, calDist)
    return


DFS(1, 0)
tmp = [0, 0]

for i in range(1, len(visited)):
    if visited[i] > tmp[1]:
        tmp[1] = visited[i]
        tmp[0] = i

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

print(max(visited))