[java]트리의 지름 - 백준1167

문제

• 트리의 지름(백준1167)

풀이

문제 해석을 하자면,

• 트리가 주어지며, 제일 큰 너비를 구하는 문제이다.

풀이

• 구글링의 힘을 조금 빌린 문제 ㅜㅜ
• DFS를 처음 임의의 노드에서 1번, 이를 통해서 찾아낸 제일 거리먼 노드에서 1번 하면 끝

코드

/**
 * 구글링의 힘을 조금 빌린 문제
 * DFS를 처음 임의의 노드에서 1번, 이를 통해서 찾아낸 제일 거리먼 노드에서 1번 하면 됨
 */
static List<Node>[] inArr = new ArrayList[100005];
static boolean[] visited = new boolean[100005];
static int V, maxNode, maxVal;

static void dfs(int val, int node) {
    // base condition -> visited
    if(maxVal < val) {
        maxVal = val; // 가중치 합
        maxNode = node; // 해당 노드
    }
    // recursion
    for(Node nxt : inArr[node]) {
        if(visited[nxt.nxt]) continue;
        visited[nxt.nxt] = true;
        dfs(val+nxt.w, nxt.nxt);
        visited[nxt.nxt] = false; // backtracking
    }
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;
    V = Integer.parseInt(br.readLine());
    for(int i = 0 ; i<V+5; i++) inArr[i] = new ArrayList<>(); // init
    for(int i = 0 ; i<V; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(stk.nextToken());
        while(true) {
            int b = Integer.parseInt(stk.nextToken());
            if(b==-1) break; // 입력 끝인지 확인
            int c = Integer.parseInt(stk.nextToken());
            inArr[a].add(new Node(b, c));
        }
    }
    // run
    visited[1] = true; // 임의의 노드 1
    dfs(0, 1);
    visited[1] = false;

    visited[maxNode] = true; // 제일 먼 노드 maxNode
    dfs(0, maxNode);
    visited[maxNode] = false;
    // output
    System.out.println(maxVal);
}
static class Node {
    int nxt, w;
    public Node(int nxt, int w) {
        this.nxt = nxt; this.w = w;
    }
}

느낀점

다시 풀어보자.