문제출처
https://www.acmicpc.net/problem/1967
문제분석
트리가 주어졌을 때 두개의 노드 사이의 거리가 최대인 경로를 찾아 그 길이를 반환하는 문제다.
문제 어디에도 이진트리라는 전제가 없다는 것에 유의해야한다.
문제접근
트리의 지름이란 가장 먼 거리에 있는 노드 사이의 경로다. 따라서 트리의 지름을 구하려면 가장 멀리 떨어져 있는 노드 둘을 구해야한다.
1. 임의의 점에서 가장 먼 노드를 찾는다(첫번째 점)
2. 첫번째 점에서 가장 먼 노드를 찾는다(두번째 점)
3. 첫번째 점과 두번째 점 사이의 경로의 길이를 구한다(트리의 지름)
그래프 상의 노드에서 가장 먼 거리의 노드를 찾아야하기 때문에 DFS를 활용한다.
노드를 방문했는지 여부를 표시하기 위해 visited 리스트를 만든다.
현재 점에서 가장 먼 노드와 그 경로를 표시하기 위해 ends 리스트를 사용한다.
DFS와 함께 visited, ends를 활용해서 가장 멀리 떨어져 있는 노드 둘과 그 사이의 거리를 구한다.
코드구현
# 백준 1967: 트리의 지름
# 2024.05.10(금) 스터디 과제
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
# 입력받기
n = int(input()) # 노드의 개수
# 그래프 입력받기
graph = [[] for _ in range(n + 1)] # 가중치 그래프 만들기
for i in range(n - 1):
parent, child, edge = map(int, input().split()) # 부모, 자식, 간선 정보 입력받기
graph[parent].append((child, edge)) # 부모 노드 기준 연결관계 정의
graph[child].append((parent, edge)) # 자식 노드 기준 연결관계 정의
# dfs 로직 준비
ends = [0,0] # 보고 있는 노드에서 (가장 먼 노드, 거리)를 갱신 및 저장
visited = [] # 방문기록 추적
def dfs(node, route):
global visited # 전역변수 visited을 그대로 씀
global ends # 전역변수 ends을 그대로 씀
visited.append(node) # 방문표시
visit_max = 1
for next in graph[node]:
if next[0] not in visited: # node의 자식노드를 아직 방문하지 않은 경우
visit_max = 0
dfs(next[0], route + next[1])
if visit_max == 1: # 마지막 노드에 도달한 경우에 ends와 비교해서 갱신 여부 결정
if route > ends[1]: # 지금 경로가 최대 경로 길이보다 길면
ends[0] = visited[-1] # 현재 방문한 노드를 먼점으로 지점
ends[1] = route # 경로 길이 갱신
visited.pop() # 스택에 가장 위의 점 pop
return
dfs(1,0)
visited.clear()
dfs(ends[0], 0)
print(ends[1])
배운점
DFS 복습
그래프의 탐색이란 하나의 정점에서 시작해서 차례대로 모든 정점들을 한번씩 방문하는 것이다.
DFS(Depth-first Search, 깊이우선탐색)이란 하나의 정점에서 탐색을 할 때 경로를 하나 지정해서 그 경로의 끝까지 탐색하는 알고리즘이다. 비교되는 알고리즘으로 BFS(너비우선탐색)이 있다.
DFS는 자기 자신을 호출한다.
DFS를 구현할 때 반드시 노드의 방문여부를 검사하는 로직을 포함해야한다.
하나의 경로를 탐색 완료한 경우에는 본래의 시작 노드로 백트래킹을 한 후 다른 경로가 있는 지 여부를 확인한다. 다른 경로가 있다면 해당 경로도 탐색을 한다.
global의 역할
ends = [0,0]
visited = [False] * (n + 1)
def dfs(node, route):
global visited
global ends
# ... 나머지 생략함수는 호출 시 별도의 스택 프레임을 받는다. 따라서 함수 내부의 변수는 함수 외부의 변수와 별도로 관리된다.
하지만 global를 사용하면 파이썬의 interpreter에게 외부의 변수를 그대로 사용하는 것으로 전달하게 된다.
따라서 global visited, global ends는 외부의 visited, ends와 동일하다.
함수 내부에서 visited와 ends를 변경하면 외부의 visited, ends도 변경된다.