[java 백준] 골드 4/ 1967번 트리의 지름

 

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

1967번: 트리의 지름

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static class Node {
        int node;
        int len;
 
        public Node(int node, int len) {
            this.len = len;
            this.node = node;
        }
 
    }
 
    public static int n;
    public static boolean[] visit;
    public static List<Node> list[];
 
    public static int realNode;
    public static int max;
 
    public static void Dfs(int x, int len) {
 
        if (len > max) {
            max = len;
            realNode = x;
        }
 
        visit[x] = true;
        for (Node nodes : list[x]) {
            if (!visit[nodes.node]) {
                visit[nodes.node] = true;
                Dfs(nodes.node, len + nodes.len);
            }
        }
 
    }
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
 
        list = new ArrayList[n + 1];
 
        for (int i = 0; i < n + 1; i++) {
            list[i] = new ArrayList<Node>();
        }
 
        for (int i = 0; i < n - 1; i++) {
            int num = sc.nextInt();
            int node = sc.nextInt();
            int len = sc.nextInt();
            list[num].add(new Node(node, len));
            list[node].add(new Node(num, len));
 
        }
        visit = new boolean[n + 1];
        Dfs(1, 0);
        visit = new boolean[n + 1];
        Dfs(realNode, 0);
 
        System.out.println(max);
 
    }
 
}
 

다익스트라 알고리즘

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

https://bumbums.tistory.com/4

자바로 만드는 다익스트라 (dijkstra) 알고리즘

 

다익스트라 알고리즘은 출발점부터 목표점까지 최단거리를 찾는데 쓰이는 알고리즘이다.

해당 노드를 방문했는지 체크하는 visit[]배열과 최단거리를 저장하는 변수 min이 있으면된다. 이 알고리즘에 대한 설명은 윗글에서 너무 잘 해주셔서 알고리즘 자체가 궁금하면 윗글을 보면되고, 나는 1967번과 관련된 다익스트라 알고리즘을 정리해볼 것이다. 

 

다익스트라 알고리즘을 반대로 생각해보면 그냥 min을 max로 바꾸고, 전체적인 생각을 뒤집기만 하면 우리가 원하는

최장거리를 구할 수 있다.

 

임의의 정점을 출발점이라 하고, 그걸 1이라 하자.

DFS(1,0) --> 시작노드에는 길이가 0임

호출하면서 가장 거리가 먼 노드를 realNode에 넣어준다.

이후 DFS(realNode,0)을 해줘서 realNode에서 가장 먼 노드까지의 길이를 max에 담아준다. 

 

 

---

1967번 질의응답 중에 좋은 답변이 있어서 가져와봤다. 이 내용도 기억해두자. 

 

https://www.acmicpc.net/board/view/59780

글 읽기 - 이 문제 다익스트라로 풀면 안되나요???

 

그래프일 경우	트리일 경우
간선의 가중치 모두 동일할 때 -> BFS 간선의 가중치 모두 다름 -> DFS	BFS,DFS 모두 사용 가능  두 정점을 잇는 경로가 유일함, 거리가 갱신되는 과정이 없기 때문