[백준] 1167번 : 트리의 지름 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1167번: 트리의 지름

 

1. 문제 설명

2. 풀이과정

해당 문제는 가장 긴 경로를 찾는 문제이다.

임의의 정점에서 가장 긴 경로로 연결돼 있는 정점은 트리의 지름에 해당하는 두 정점 중 하나라는 아이디어를 가지고 문제를 해결해 본다.

 

각 정점에 대한 간선의 정보를 가지고 그래프를 인접 리스트로 저장한다.

인접 리스트로 저장할 때는 [정점, 거리]의 형식으로 그래프에 저장한다.

임의의 정점 중 정점 1에서 탐색을 진행하며 각 정점 별 연결되어 있는 정점의 거리를 기록한다.

위의 정점 1에서 가장 긴 경로로 연결돼 있는 정점은 트리의 지름에 해당하는 두 정점 중 하나라는 아이디어를 고려하여 정점 1에서 가장 긴 경로를 가지는 정점을 찾아 해당 정점부터 다시 탐색을 진행하여 각 정점별 연결되어 있는 정점의 거리를 기록한다.

다시 구한 거리 중 가장 큰 값(가장 긴 경로)이 트리의 지름이 된다.

 

슈도코드

1. V(노드 개수) 입력받기
2. graph(그래프 데이터 저장할 인접 리스트) 생성
3. for V만큼 반복: graph 인접 리스트에 그래프 데이터 저장 ([정점, 가중치] 형식으로)
4. visited(방문 기록) 리스트 초기화
5. distance(거리 기록) 리스트 초기화
6. def BFS(v):
   1. 큐 자로구조 생성 및 시작 정점 삽입
   2. visited 리스트에 현재 정점 방문 기록
   3. while (큐가 비어 있을 때까지):
      1. 큐에서 정점 데이터 가져오기 (제일 앞 데이터)
      2. for 현재 정점의 연결 정점:
         1. if (미 방문 정점):
            1. visited 리스트에 방문 기록
            2. 큐에 정점 삽입
            3. 큐에 삽입된 노드 거리 = 현재 노드의 거리 + 간선의 거리로 변경
7. BFS(임의의 점 1을 시작점으로) 실행
8. distance 리스트에서 가장 큰 값을 가지는 정점(인덱스)을 시작점으로 지정
9. 새로운 탐색을 위해 visited 리스트와 distance 리스트 초기화
10. BFS(새로운 시작점으로) 실행
11. distance 리스트에서 가장 큰 수를 정답으로 출력

반응형

3. 소스코드

import sys
from collections import deque

V = int(sys.stdin.readline())

graph = [[] for _ in range(V + 1)]
for _ in range(V):
    info = list(map(int, sys.stdin.readline().split()))
    for i in range(1, len(info) - 1, 2):
        graph[info[0]].append([info[i], info[i + 1]])

visited = [False] * (V + 1)
distance = [0] * (V + 1)

def BFS(v):
    queue = deque()
    queue.append(v)
    visited[v] = True
    
    while (queue):
        new = queue.popleft()
        for i in graph[new]:
            if (not visited[i[0]]):
                visited[i[0]] = True
                queue.append(i[0])
                distance[i[0]] = distance[new] + i[1]

BFS(1)
index = distance.index(max(distance))

visited = [False] * (V + 1)
distance = [0] * (V + 1)

BFS(index)
print(max(distance))