백준/Python) 19581 두번째 트리의 지름 - DFS

💭 나의 접근 방법

---

이 문제를 풀기 이전에 트리의 지름 문제를 2개 풀고 이 문제를 접하게 되었다.

 

<트리의 지금 접근 방식>

임의의 지점에서 가장 먼 지점 A / A에서 가장 먼 지점 B 

B의 거리가 트리의 지름이 된다.

 

내가 생각한 두번째 트리의 지름은 

A 까지의 탐색의 DFS와 B까지의 탐색의 DFS의 max 값을 갱신해주어 문제를 풀려고 접근하였다.

이 접근방식은 고려되지 않은 지점에서 트리의 길이가 나올수 있기때문에 틀린 접근 방법이었다.

 

이 문제의 접근 방법은

1️⃣임의의 지점에서 가장 먼 지점 A / A에서 두번째로 먼 지점 B

2️⃣임의의 지점에서 두번째로 먼 지점 C / C에서 가장 먼 지점 D

방법으로 문제를 접근해야한다.

 

다만 이 문제의 예외사항이 있다.

예제 2번의 경우이다.

3
1 2 3
1 3 2

 

이 입력은 접근방법 1️⃣,2️⃣번에서의 지름이 같게 나오기때문에 2️⃣번의 C -> D 부분은 두번째로 먼 지점을 구하여 풀어주었다.

 

 

💡 결과

---

# 19581 두번째 트리의 지름 G1
'''
임의의 지점에서 가장 먼 지점 A / A에서 두번째로 먼 지점 B
임의의 지점에서 두번짹로 가장 먼 지점 C / C에서 가장 먼 지점 D
https://dlwnsdud205.tistory.com/86 c++언어 파이썬으로 해석
'''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
graph = [[] for _ in range(N+1)]
distance1 = [-1] * (N+1)
distance2 = [-1] * (N+1)
visited = [0] * (N+1) 
for _ in range(N-1):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

def DFS(x,wei,distance1,distance2):
    for i in graph[x]:
        b,c = i
        if distance1[b] == -1:
            distance1[b] = max(distance2[b],c+wei)
            DFS(b,c + wei,distance1,distance2)

distance1[1] = 0
DFS(1,0,distance1,distance2)

# 임의의 지점에서 가장 먼 지점 A / A에서 두번째로 먼 지점 B
firstIdx = distance1.index(max(distance1))
distance1[firstIdx] = -1

distance2[firstIdx] = 0
DFS(firstIdx,0,distance2,distance1)
large = max(distance2)
distance2.remove(max(distance2))
result = []
result.append(max(distance2))

# 임의의 지점에서 두번짹로 가장 먼 지점 C / C에서 가장 먼 지점 D
distance2 = [-1] * (N+1)
secondIdx = distance1.index(max(distance1))
distance2[secondIdx] = 0
DFS(secondIdx,0,distance2,distance1)

# 예제 2번과 같이 두가지 경우의 거리가 같은 경우 2번 경우의 두번째 지점을 비교하게 한다.
if max(distance2) == large:
    distance2[distance2.index(max(distance2))] = -1
result.append(max(distance2))

# 두가지 경우중에 가장 큰 거리
print(max(result))

 

 

💫 느낀점

---

코드가 조금 중구난방하지만 충분히 다시 정리할수 있을것 같다. 

 

 

 

 

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

19581번: 두 번째 트리의 지름