트리의 지름

문제풀이

dfs, bfs로 풀면 되는 문제다. 문제를 잘 읽자..

주의할 점! 주어지는 간선들의 정보가 주어진 정점의 순서대로가 아니다!

    ex)
    5
    1 3 2 -1
    2 4 4 -1
    3 1 2 4 3 -1
    4 2 4 3 3 5 6 -1
    5 4 6 -1
    위와 같이 주어질 수 있지만,
    5
    5 4 6 -1
    3 1 2 4 3 -1
    4 2 4 3 3 5 6 -1
    2 4 4 -1
    1 3 2 -1
    이렇게 주어질 수도 있다.

    4%까지가서 틀린다면, 이 경우를 확인해봐야한다.
  

소스코드

DFS

const log = console.log;
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// const input = fs.readFileSync("./stdin").toString().trim().split("\n");

const vertex = +input[0];
let edge = input.slice(1, vertex+1).map(e => e.split(" ").map(el => +el));
edge = edge.reduce((acc, val) => {
  const [index, ...rest] = val;
  acc[index-1] = val;
  return acc;
},[]);
const visited = Array(vertex).fill(false);
let d = 0;
let node = 1;

const dfs = (start, acc, visited) => {
  visited[start-1] = true;
  if(d < acc){
    d = acc;
    node = start;
  }
  for(let i=1 ; i<edge[start-1].length ; i += 2){
    if(edge[start-1][i] === -1) break;
    if(visited[edge[start-1][i]-1]) continue;
    dfs(edge[start-1][i], acc+edge[start-1][i+1], visited);
  }
}

dfs(1, 0, [...visited]);
dfs(node, 0, [...visited]);
log(d);

BFS

const log = console.log;
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// const input = fs.readFileSync("./stdin").toString().trim().split("\n");

const vertex = +input[0];
let edge = input.slice(1, vertex+1).map(e => e.split(" ").map(el => +el));
edge = edge.reduce((acc, val) => {
  const [index, ...rest] = val;
  acc[index-1] = val;
  return acc;
},[]);
const visited = Array(vertex).fill(false);
let d = 0;
let node = 1;

class Queue{
  arr = [];
  head = 0;
  tail = 0;

  push(value){    
    if(value instanceof Array){
      this.arr.push(...value);
      this.tail += value.length;
    }else{
      this.arr.push(value);
      this.tail++;
    }
  }

  shift(){
    if(this.size() === 0) return undefined;
    return this.arr[this.head++];
  }

  size(){
    return this.tail - this.head;
  }
}

const bfs = (start, visited) => {
  const queue = new Queue();
  queue.push({ s:start, c:0 });
  while(queue.size()){
    const { s, c } = queue.shift();
    for(let i=1 ; i<edge[s-1].length ; i +=2 ){
      if(edge[s-1][i] === -1) break;
      if(visited[edge[s-1][i]-1]) continue;
      queue.push({ s: edge[s-1][i], c: edge[s-1][i+1] + c });
      if(d < edge[s-1][i+1] + c){
        d = edge[s-1][i+1] + c;
        node = edge[s-1][i];
      }
    }
    visited[s-1] = true;
  }
}
bfs(1, [...visited]);
bfs(node, [...visited]);
log(d);