티스토리 뷰
https://www.acmicpc.net/problem/1967
1967번: 트리의 지름
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연
www.acmicpc.net
난이도 : 골드 4
가장 긴 지름을 만드는 노드 node1과 node2가 있다고 가정한다면, 임의의 노드 1개에서 가장 먼 노드는 node1이나 node2 일 것입니다.
여기서 긴 지름에 참여하는 노드 1개를 구하고 나머지 하나의 노드를 구하면 node1과 node2를 둘 다 구할 수 있습니다.
가장 먼 노드는 dfs로 구했습니다.
https://www.acmicpc.net/problem/1167
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지
www.acmicpc.net
같은 방식으로 위 문제 또한 풀 수 있습니다.
전역 변수
LinkedList<Edge> tree[] = 노드들의 연결 정보를 저장하는 배열
int distance[] = 출발 노드부터 각 노드까지의 거리
int max, index = 출발 노드로부터 가장 먼 거리 max와 그 노드의 번호 index
boolean visit[] = dfs 할 때 각 노드의 방문 여부를 저장
함수
void main
입력을 받고 전역 변수들을 세팅해줍니다. 트리는 무방향 그래프이므로 잘 연결해줍니다.
노드가 1개만 있을 경우도 예외 처리해줍니다.
총 2번의 dfs를 합니다. 첫 번째는 임의의 노드(1)에서 가장 먼 노드를 구하고, 이 구한 노드로부터 가장 먼 노드를 구합니다.
(dfs 호출)
void dfs
node 번호와 가중치를 파라미터로 dfs합니다.
현재 노드의 가중치를 최대 값으로 계속 업데이트하고 그때의 노드 번호를 index에 저장합니다.
연결된 노드 중 방문하지 않은 노드를 dfs합니다.
(dfs 호출)
class Edge
간선의 정보를 저장합니다. 연결된 노드 번호 number와 가중치 weight를 가집니다.
1167 트리의 지름 정답 코드
'문제풀이 > 백준 && 프로그래머스' 카테고리의 다른 글
| [백준 3860] 할로윈 묘지 (자바) (0) | 2020.12.01 |
|---|---|
| [백준 1865] 웜홀 (자바) (0) | 2020.11.27 |
| [백준 1944] 복제 로봇 (자바) (0) | 2020.11.08 |
| [백준 1197] 최소 스패닝 트리 (자바) (0) | 2020.11.08 |
| [백준 4386] 별자리 만들기 (자바) (0) | 2020.11.08 |