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

문제



풀이

문제 해석을 하자면,

  • 트리는 무방향이며, 제일 큰 너비를 구하는 문제이다.


풀이

  • 이전에 풀었던 “트리의 지름” 문제와 매우 유사하므로 해당 풀이 게시물도 참고
  • 여기서 루트 노드 1로 고정 해주지만, 사실 BOJ 1167을 풀었다면 루트 노드가 무엇이든 상관 없이 풀 수 있을것이다.
  • 무방향 그래프라고 언급했으므로 주의 => BOJ 1167 과 유일하게 달랐던 부분
  • 이곳에서도 핵심 풀이는 DFS를 처음 임의의 노드에서 1번, 이를 통해서 찾아낸 제일 거리먼 노드에서 1번 하는 것이다.



코드

/**
 * 루트 노드 1로 고정 해주지만, 사실 BOJ 1167을 풀었다면 루트 노드가 무엇이든 상관 없이 풀 수 있을것이다.
 * 무방향 그래프라고 언급했으므로 주의 => BOJ 1167 과 유일하게 달랐던 부분
 * 이곳에서도 핵심 풀이는 DFS를 처음 임의의 노드에서 1번, 이를 통해서 찾아낸 제일 거리먼 노드에서 1번 하는 것이다.
 */
static List<Node>[] inArr = new ArrayList[10005];
static boolean[] visited = new boolean[10005];
static int 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;
    int N = Integer.parseInt(br.readLine());
    for(int i = 0; i<N+5; i++) inArr[i] = new ArrayList<>();
    for(int i = 0 ; i<N-1 ; i++){
        stk = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(stk.nextToken());
        int b = Integer.parseInt(stk.nextToken());
        int c = Integer.parseInt(stk.nextToken());
        inArr[a].add(new Node(b, c));
        inArr[b].add(new Node(a, c)); // 무방향
    }
    // run
    visited[1] = true;
    dfs(0, 1); // 임의의 노드 1
    visited[1] = false; // backtracking

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



느낀점

생략

댓글남기기

참고