728x90 반응형 너비 우선 탐색1 [백준] 1167번 : 트리의 지름 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 가장 긴 경로를 찾는 문제이다. 임의의 정점에서 가장 긴 경로로 연결돼 있는 정점은 트리의 지름에 해당하는 두 정점 중 하나라는 아이디어를 가지고 문제를 해결해 본다. 각 정점에 대한 간선의 정보를 가지고 그래프를 인접 리스트로 저장한다. 인접 리스트로 저장할 때는 [정점, 거리]의 형식으로 그래프에 저장한다. 임의의 정점 중 정점 1에서 탐색을 진행하며 각 정점 별 연결되어 있는 정점의 거리를 기록한다.. 2024. 1. 19. 이전 1 다음 728x90 반응형
