[파이썬] 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

 

 

🌿 나의 풀이

# 트리의 지름을 구하는 문제
# 1번 노드에서 가장 먼 노드를 구하고 dfs를 다시 호출해서 거리를 구했다
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

V = int(input())        # 정점의 개수
answer = 0
dic = defaultdict(set)      # 정점A : 정점A와 연결된 정점들
distance_dic = dict()       # (정점A, 정점B) : 정점A와 정점B 사이의 거리
visit = [0] * (V+1)
node = 1
for v in range(V) :
    input_lst = list(map(int, input().split()))
    node = input_lst[0]
    for i in range(1, len(input_lst)-1, 2) :
        dic[node].add(input_lst[i])
        distance_dic[(node, input_lst[i])] = input_lst[i+1]
        distance_dic[(input_lst[i], node)] = input_lst[i+1]

def dfs(cur, distance) :
    global answer, node

    if answer < distance :
        answer = max(answer, distance)
        node = cur

    for val in dic[cur] :
        if not visit[val] :
            visit[val] = 1
            dfs(val, distance + distance_dic[(cur, val)])
            visit[val] = 0

visit[1] = 1
dfs(1, 0)
visit[1] = 0
visit[node] = 1
dfs(node, 0)

print(answer)       # 트리의 지름

아래의 풀이와 다른점은 dfs를 실행한 후 1번 노드를 0으로 초기화해준 것이다.

이 과정을 생략하면 거리를 구할 때 1번 노드와 연결된 노드에 방문하지 못한다.

 

 

# 틀렸습니다
from collections import defaultdict
import sys
input = sys.stdin.readline

V = int(input())        # 정점의 개수
answer = 0
dic = defaultdict(set)      # 정점A : 정점A와 연결된 정점들
distance_dic = dict()       # (정점A, 정점B) : 정점A와 정점B 사이의 거리
visit = [0] * (V+1)
node = 1
for v in range(V) :
    input_lst = list(map(int, input().split()))
    node = input_lst[0]
    for i in range(1, len(input_lst)-1, 2) :
        dic[node].add(input_lst[i])
        distance_dic[(node, input_lst[i])] = input_lst[i+1]
        distance_dic[(input_lst[i], node)] = input_lst[i+1]

def dfs(cur, distance) :
    global answer, node

    if answer < distance :
        answer = max(answer, distance)
        node = cur

    for val in dic[cur] :
        if not visit[val] :
            visit[val] = 1
            dfs(val, distance + distance_dic[(cur, val)])

visit[1] = 1
dfs(1, 0)
visit[node] = 1
dfs(node, 0)
print(answer)       # 트리의 지름

50%까지 맞았는데 틀렸다고 떴다.

 

 

# 틀렸습니다
from collections import defaultdict
import sys
input = sys.stdin.readline

V = int(input())        # 정점의 개수
answer = 0
dic = defaultdict(set)      # 정점A : 정점A와 연결된 정점들
distance_dic = dict()       # (정점A, 정점B) : 정점A와 정점B 사이의 거리
visit = [0] * (V+1)
for v in range(V) :
    input_lst = list(map(int, input().split()))
    node = input_lst[0]
    for i in range(1, len(input_lst)-1, 2) :
        dic[node].add(input_lst[i])
        distance_dic[(node, input_lst[i])] = input_lst[i+1]
        distance_dic[(input_lst[i], node)] = input_lst[i+1]

def dfs(cur, distance) :
    global answer

    answer = max(answer, distance)

    for val in dic[cur] :
        if not visit[val] :
            visit[val] = 1
            dfs(val, distance + distance_dic[(cur, val)])

dfs(1, 0)
print(answer)       # 트리의 지름

dfs를 한 번만 실행해서 트리의 지름을 구할 수 없다.

1번 노드에서 가장 먼 노드까지의 트리의 지름이 문제에서 요구하는 트리의 지름이 될 수 없다.

테케를 통과해서 맞을 줄 알았던...🤣

 

 

🔥 다른 사람 풀이

# https://velog.io/@coding_egg/%EB%B0%B1%EC%A4%80-1991%EB%B2%88-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC
from sys import stdin
from collections import deque

read = stdin.readline
V = int(read())
graph = [[] for _ in range(V + 1)]

for _ in range(V) :
    c = list(map(int, read().split()))
    for e in range(1, len(c) - 2, 2) :
        graph[c[0]].append((c[e], c[e + 1]))

def bfs(start) :
    visit = [-1] * (V + 1)
    que = deque()
    que.append(start)
    visit[start] = 0
    _max = [0, 0]

    while que :
        t = que.popleft()
        for e, w in graph[t] :
            if visit[e] == -1 :
                visit[e] = visit[t] + w
                que.append(e)
                if _max[0] < visit[e] :
                    _max = visit[e], e
    return _max

dis, node = bfs(1)
dis, node = bfs(node)
print(dis)

BFS 탐색

임의로 1번 노드에서 시작해서 가장 먼 노드를 구한다.

구한 노드에서 가장 먼 노드와의 거리를 구한다.

 

 

문제 출처 👉 백준