[백준 1967] 트리의 지름 (자바) && [백준 1167] 트리의 지름 (자바)

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

난이도 : 골드 4

 

가장 긴 지름을 만드는 노드 node1과 node2가 있다고 가정한다면, 임의의 노드 1개에서 가장 먼 노드는 node1이나 node2 일 것입니다.

여기서 긴 지름에 참여하는 노드 1개를 구하고 나머지 하나의 노드를 구하면 node1과 node2를 둘 다 구할 수 있습니다.

가장 먼 노드는 dfs로 구했습니다.

 

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

같은 방식으로 위 문제 또한 풀 수 있습니다.

---

전역 변수

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 트리의 지름 정답 코드