백준 1967번 트리의 지름 G4 - 트리, dfs

트리 지름이고 뭐고 옷 지름기 하고싶다.

 

 

 

먼저 문제를 잘 읽어보자.

트리의 그래프에 가중치가 있는채로 들어가 있고, 양쪽으로 쫙 당길때 -> 서로 끝과 끝일때 란 얘기.

결국 트리의 리프노드를 찾아서 거리계산하면 되는구나! 라는 접근법에 도달했다.

ㅋㅋ 아 시작은 거창하죠

 

 

import java.io.*;
import java.util.*;
 
 
public class Main { //Boj_1967_트리의 지름
    // 상하좌우
    static int[][] arr;
    static boolean[] visit;
    static Set<Integer> leaf;
    static int N, M, answer;
 
    // 일직선으로 가장 긴 거리 == 현재 노드에서 여러 갈래 중 경로가 겹치지 않는 가장 긴 두 선
    // 아예 말단에서 시작하면 되는데? 맨밑에서 맨밑으로 연결 -> 지름, 리프 -> 리프
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N + 1][N + 1];
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
 
            arr[start][end] = value;
            arr[end][start] = value;
        }
 
        int root = 1;
        leaf = new HashSet<>();
        find_leafNode(root);
//        System.out.println(leaf); // 디버깅
//        System.out.println(arr);
        answer = -1;
        visit = new boolean[N + 1];
        for (int i : leaf) {
            visit[i] = true;
            int max = 0;
            dfs(i, i, max, visit);
        }
        System.out.println(answer);
    }
 
    public static void find_leafNode(int start) {
        boolean[] visit = new boolean[N + 1];
        Queue<Integer> que = new LinkedList<>();
        que.add(start);
        visit[start] = true;
 
        while (!que.isEmpty()) {
            int now = que.poll();
            boolean isLeaf = true;
 
            for (int i = 1; i <= N; i++) {
                if (arr[now][i] != 0 && !visit[i]) {
                    que.add(i);
                    visit[i] = true;
                    isLeaf = false;
                }
            }
 
            if (isLeaf) {
                leaf.add(now);
            }
        }
    }
 
    public static void dfs(int start, int now, int max, boolean[] visit) {
        if(now != start && leaf.contains(now)){
            answer = Math.max(answer,max);
            System.out.println("now : " + now);
            System.out.println("max = " + max);
            return;
        }
 
        for(int i = 1; i<=N; i++){
            if(arr[now][i] != 0 && !visit[i]){
                visit[i] = true;
                dfs(start, i, max + arr[now][i], visit);
                visit[i] = false;
            }
        }
 
    }
}

 

먼저 코드를 보게되면 bfs 식으로 que를 활용해서 자식 노드가 없다면 리프노드이다! 라는 함수를 짜주었다.

이후 리프노드들을 leaf 리스트에 모아서 dfs를 굴려줬는데,,, 

 

ㅋㅋ 어 그거 아니야

 

노드가 10,000개 까지라 메모리가 석나가버렸다... (돌아와 줘)

이차원 배열을 사용했기에 뭐 1억.. 써버렸으니 머

 

어떻게 가지치기를 할까 하다가 인접 리스트로 다시 구현하고, 로직을 수정하고자 했다.

어짜피 우린 가중치가 큰 경로를 찾아야 하므로 루트에서 가장 가중치가 크고 먼 노드를 찾고(리프노드)

한번 더 돌려서 해당 리프에서 가장 멀고 가중치가 높은곳을 찾아주면 된다...!

 

시간복잡도가 한참 줄었다.. input이 1만이라면 1만 체크하고 9999번 하면 그만이니깡.

이전 코드의 경우 BFS 할때 나온 리프노드의 개수에 따라서 복잡도가 크게 달라졌을것이다. 

 

import java.io.*;
import java.util.*;
 
class Node {
    int now, dist;
    Node(int now, int dist) {
        this.now = now;
        this.dist = dist;
    }
}
 
public class Main { //Boj_1967_트리의 지름
    static List<List<Node>> tree;
    static boolean[] visit;
    static int N;
    static int max;
    static int far_Node;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
 
        tree = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            tree.add(new ArrayList<>());
        }
 
        for (int i = 1; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            tree.get(start).add(new Node(end, weight));
            tree.get(end).add(new Node(start, weight));
        }
        // 가장 먼 노드 찾기.
        visit = new boolean[N + 1];
        dfs(1, 0);
 
        visit = new boolean[N + 1];
        dfs(far_Node, 0);
 
        System.out.println(max);
    }
 
    public static void dfs(int node, int value) {
        visit[node] = true;
 
        if (value > max) { // 합이 더 크다면 멀다고 판단.
            max = value;
            far_Node = node;
        }
 
        for (Node next : tree.get(node)) {
            if (!visit[next.now]) {
                dfs(next.now, value + next.dist);
            }
        }
    }
}

 

개운..