[BOJ_1967] 트리의 지름

1967번: 트리의 지름

 

✅ 문제 설명

트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 트리의 지름이라고 정의할 때, 트리의 지름을 구하는 문제입니다.

 

✅ 접근 방식

트리의 지름을 구하는 방법은 다음과 같습니다.
1) 시작노드(=아무노드나 가능)에서 가장 먼 노드 A를 구합니다.
2) 노드 A를 기준으로 가장 먼 노드B를 구하면 그 두 노드(A,B) 사이의 거리가 트리의 지름이 됩니다.

---

• 이게 왜 가능할까요?
• 어떤 노드에서 가장 먼 노드를 구하면(1번) 그 노드가 지름의 양 끝 점 중 하나가 됩니다. 
  -> 이렇게 되는 이유에 관한 제 나름대로의 의견은 다음과 같습니다! :>

• 따라서 지름의 끝에서 가장 먼 노드를 구하면(2번) 그 노드가 지름의 다른 한쪽 끝이 되어서 두 노드 사이가 트리의 지름이 되는 것입니다.

---

 

그럼 이제 이해가 되었으니 이 방법을 이용해 코드를 작성해봅시다!

1) 시작노드(=아무노드나 가능)에서 가장 먼 노드 A를 구합니다.
2) 노드 A를 기준으로 가장 먼 노드B를 구하면 그 두 노드(A,B) 사이의 거리가 트리의 지름이 됩니다.

 

✅ 코드 설명

n = int(sys.stdin.readline())
tree = [[] for _ in range(n + 1)]

for i in range(n - 1):
    parent, child, weight = map(int, sys.stdin.readline().split())
    tree[parent].append([child, weight])
    tree[child].append([parent, weight])

지금까지의 포스팅에서는 tree를 구성할 때, child node만 적어주는 식으로 루트에서 child로 내려오는 방향 하나만 기록해줬는데 이번 문제는 루트에서만 그래프를 탐방하는게 아니라 양방향으로 정보를 입력해주었습니다.

 

def dfs(start, distance):
    for node, weight in tree[start]:
        if visited[node] == -1:
            visited[node] = distance + weight
            dfs(node, visited[node])

dfs 코드는 다음과 같습니다. start 노드에 연결되어있는 node와 그 node의 weight 정보를 하나씩 꺼내와서 그 노드가 방문하지 않은 노드라면, visited[node]를 distance + weight로 업데이트 해줍니다. 이 값은 start 노드에서 해당 node까지의 길이를 뜻합니다. 그리고 재귀적으로 dfs를 수행해줍니다. 인자로는 현재 노드인 node와 시작노드에서 그 노드까지의 거리값인 visited[node]를 넘겨줍니다.

 

visited = [-1] * (n + 1)

# 임의 노드(i) 
i = 1  # 1~n까지 아무 노드나 해도 가능! 일단 루트노드가 1로 주어졌으니 루트노드로 해주었다.
visited[i] = 0
dfs(i, 0)
# visited 리스트에서 가장 큰 값을 가진 요소의 인덱스를 찾습니다.
far_node = visited.index(max(visited))

위에서 설명했던 1)번 과정입니다.  visited 배열을 방문하지 않았다는 뜻으로 모두 -1로 초기화해줍니다. 이후 임의노드를 시작점으로 잡고 방문했다&시작점이라 거리가 0이라는 뜻으로 visited[i]=0으로 정해주고 dfs(i,0)을 해줍니다. i가 시작점이므로 시작점으로부터 현재노드까지의 거리가 0이므로 dfs의 인자값으로 0을 주었습니다. 

visited 배열에 저장되어있는 최대값의 인덱스값이 시작노드로부터 가장 먼 노드의 번호입니다. (visited에 시작노드~해당노드까지의 거리를 저장했으므로) -> 시작노드로부터 가장 먼 노드(=지름의 양끝점 중 하나)의 번호를 far_node로 설정해주었습니다.

 

visited = [-1] * (n + 1)
visited[far_node] = 0
dfs(far_node, 0)

print(max(visited))

2)번 과정입니다. visited 배열을 다시 -1로 초기화 해주고, 이번엔 아까 1)번 과정에서 찾아둔 far_node를 기준으로 가장 먼 노드를 찾습니다. dfs를 진행하면서 visited에 far_node로부터 각각 노드까지의 거리가 저장되므로,  visited.index(max(visited))가 far_node로 부터 가장 먼 노드의 번호이자 지름의 다른쪽 끝점이 되는데 우리는 문제에서 지름의 값만 요구하였으므로 max(visited)를 출력해주면 문제 해결입니다!

 

✅ 최종 코드

# 트리의 지름

import sys
sys.setrecursionlimit(10 ** 4)

n = int(sys.stdin.readline())
tree = [[] for _ in range(n + 1)]

for i in range(n - 1):
    parent, child, weight = map(int, sys.stdin.readline().split())
    tree[parent].append([child, weight])
    tree[child].append([parent, weight])


def dfs(start, distance):
    for node, weight in tree[start]:
        if visited[node] == -1:
            visited[node] = distance + weight
            dfs(node, visited[node])


visited = [-1] * (n + 1)

# 임의 노드(i) 
i = 1  # 1~n까지 아무 노드나 해도 가능! 일단 루트노드가 1로 주어졌으니 루트노드로 해주었다.
visited[i] = 0
dfs(i, 0)
# visited 리스트에서 가장 큰 값을 가진 요소의 인덱스를 찾습니다.
far_node = visited.index(max(visited))

visited = [-1] * (n + 1)
visited[far_node] = 0
dfs(far_node, 0)

print(max(visited))

 

❇️ 코멘트

• 저는 문제를 풀면서 "어떤 노드에서 가장 먼 노드를 구하면 그 노드가 지름의 양 끝 점 중 하나가 된다."는 부분이 잘 이해가 가지 않았었는데, 여러분은 제 포스팅을 보고 약간의 도움이 되었으면 좋겠네요! :> 
• sys.setrecursionlimit(10**4)을 사용하지 않으면 recursionError가 나니 주의해주세요!

---

• 뭔가 개인적으로는 sys.setrecursionlimit(10**4) 을 쓰면 인위적으로 푼 것 같아 마음이 좋진 않지만.. 더 좋은 방법을 모르겠습니다.. 하핫 (재귀로 안 푸는 방법도 생각해봐야겠어요)
• dfs말고도 bfs로도 풀이하신 블로그를 보았는데 bfs로도 풀어서 추가 업데이트 하겠습니다.