[PS] 백준1967 : 트리의 지름(Java)

문제

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

 

---

풀이

깊이 우선 탐색(DFS) 활용한 풀이

접근법

1. 각 노드에서 순회(dfs)
2. 방문체크를 통해 한쪽 깊이로만 탐색
3. 더 이상 탐색이 불가능한 노드에 도착 시 최대값 비교 및 갱신

문제에서 “트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우” 라는 문맥을 통해서 두 노드 사이를 순회하여 제일 높은 가중치를 구하면 되겠구나 라는 생각을 함.

 

해당 문제를 풀며 조금 생각이 필요했던 부분은 특정한 노드에서 부모노드로 순회를 하게되는 경우였음.

이번에 접근한 방식으로는 클래스 배열을 활용하여 부모노드에 대해 기록을 한 뒤 순회를 하도록 구현하였음. (자세한 부분은 아래코드를 참조)

---

소스코드

import java.io.*;
import java.util.*;

//BOJ_1967 트리의 지름
public class Main {
    static class Node {
        int v;
        int w;
        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    static List<List<Node>> list;
    static Node[] parentArr; //부모 노드의 정보를 기록하는 배열
    static int N, res;
    static boolean[] v;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        //dfs?
        /**
         * 제일 긴 가중치로 연결하면되나?
         * 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우
         * 1. 각 정점에서 순회 시작(dfs)
         * 2. 한쪽 깊이로 탐색 (visited 체크)
         * 3. 더 이상 탐색할 수 없는 곳까지 탐색완료한 경우 res 최대값 갱신?
         * 일단 내 풀이로 풀려면 부모, 자식 둘 다 탐색해야함.
         *
         * **/

        N = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        for(int i=0; i<=N; i++) list.add(new ArrayList<>());
        parentArr = new Node[N+1];

        for(int i=0; i<N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int current = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            Node parentNode = new Node(parent, weight);
            Node childNode = new Node(current, weight);
            parentArr[current] = parentNode;    //부모노드 기록
            list.get(parent).add(childNode);    //단방향
        }

        for(int i=1; i<=N; i++) {
            v = new boolean[N+1];
            dfs(i, 0);
        }

        System.out.println(res);
    }

    static void dfs(int node, int sum) {

        //기저조건 : leaf Node 방문 시? 다음 탐색 가능한 곳이 없을 경우 최대값 비교
        v[node] = true;
        // 자식 노드 탐색
        for(Node n : list.get(node)) {
            if(!v[n.v]) {
                dfs(n.v, sum + n.w);
            }
        }

        // 부모 노드 탐색
        if(parentArr[node] != null && !v[parentArr[node].v]) {
            dfs(parentArr[node].v, sum + parentArr[node].w);
        }

        v[node] = false; //백트래킹
        //탐색 종료 시
        res = Math.max(res, sum);
    }
}

 

---

정리

 

프로젝트 집중 기간이 지난 후 알고리즘 재활치료 겸 선택했던 문제..

처음에 문제를 읽었을 때는 조금 뇌절이 왔는데, 천천히 문맥과 조건을 읽어보며 실마리를 찾아나갔고, 그 결과 첫 접근을 통해서 한번에 풀 수 있었다..

 

하지만 그 결과는 처참… 시간복잡도, 공간복잡도가 확실히… 다른 사람의 풀이도 한번 참조해서 정리해봐야 될 것 같음!

이번 문제를 통해서 재활치료 꾸준히 해야겠구나 라는 생각을 했고, 오랜만에 PS 포스팅도 올리게 되었음

 

재활치료 꾸준하게 해서 하반기 기업 코테 전부 뿌셔보자!!!