[JS][백준]1167_트리의 지름

문제 번호

1167번: 트리의 지름

 

 

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 깊이 우선 탐색

 

문제 풀이

 DFS를 활용한다. 그전에 트리의 지름에 대해서 찾아보면 많은 자료들이 나온다. 처음에는 그래프 탐색까지만 감을 잡고 생각을 해보았는데 나중에 트리의 지름에 대해서 검색해보니 알고리즘은 쉽게 이해할 수 있었다.

 

트리의 지름 구하기

 간단하게 말하자면 트리의 지름을 구하는 방법은 다음과 같다. 임의의 정점 X가 있을 때 X에 대해서 가장 멀리 있는 정점 Y를 구한다. 이제 정점 Y에 대해서 가장 멀리 있는 정점에 대한 거리를 구하면 그 거리가 트리의 지름이 된다.

 

 나는 백준 질문게시판에 다음 글을 보고 문제를 풀 수 있었다.

글 읽기 - [힌트] 야매 증명 이지만 직관적으로 이해되는 증명. 저처럼 헤매지 마세요.

 

 이제 구현만 하면된다. 2번의 DFS로 트리의 지름을 구할 수 있다.

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const V = +input[0];
let g = new Array(V + 1).fill(null).map(_ => []);

function DFS(start) {
  let ret = {
    no: 0,
    dist: 0,
  };

  let visited = new Array(V + 1).fill(false);
  let s = [];
  s.push({
    no: start,
    dist: 0,
  });

  while (s.length !== 0) {
    let cur = s.pop();
    let [curNode, curDist] = [cur.no, cur.dist];    
    if (curDist >= ret.dist) {
      ret.no = curNode;
      ret.dist = curDist;
    }

    if (!visited[curNode]) {
      visited[curNode] = true;
      for (let next = 0; next < g[curNode].length; next++) {
        if (!visited[g[curNode][next].to]) {          
          s.push({
            no: g[curNode][next].to,
            dist: curDist + g[curNode][next].dist,
          })
        }
      }
    }
  }
  
  return ret;
}
function main() {
  let start = 0;
  for (let i = 1; i < input.length; i++) {  // 간선 정보 입력. 10^5.
    input[i] = input[i].trim().split(' ').map(Number);        
    let node = input[i][0];  // 정점. ???????????  근데 어떻게 답은 잘 나왔냐? 그냥 예제로 넣은게 운이좋았다.        
    start = node;    
    for (let j = 1; j < input[i].length; j += 2) { // ?
      if (input[i][j] === -1)
        break;
      g[node].push({  // node -> to 로 갈때 dist만큼의 거리가 있다.
        to: input[i][j],
        dist: input[i][j + 1],
      })      
    }
  }    
  
  let farNode = DFS(start).no;  // 임의의 노드와 가장 멀리있는 노드를 구한다.  
  let answer = DFS(farNode).dist;  // '위에서 구한 가장 멀리있는 노드'와 가장 멀리있는 노드와의 거리를 구한다.
  
  return console.log(answer.toString().trim());
}
main();

 

항상 입력을 받거나 데이터를 처리할 때 주의를 두고 해야겠다.

 input[i] = input[i].trim().split(' ').map(Number);        
    let node = input[i][0];  // 정점. ???????????  근데 어떻게 답은 잘 나왔냐? 그냥 예제로 넣은게 운이좋았다.

해당 부분을 처리할때 두 줄의 순서를 바꿔서 쓰는 바람에 왜 틀렸는지를 몰라서 한참을 고생했다. 더욱이 질문게시판의 반례들도 운 좋게 통과가 되어서 저걸 알아차리는데 더 오래 걸렸다. 저 순서를 바꿔서 쓰면 노드의 번호가 2자리를 넘어갈 때 온전한 숫자를 입력받지 못하고 맨 앞의 한자리만 잘라서 받아오게 된다. ex) 10이면 '10'이 아니라 '1'만 받아옴.

 

시도했던 반례들

5
5 4 6 -1
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
답 11
5
1 5 1 -1
5 1 1 4 10 -1
4 3 10 5 10 -1
3 2 10 4 10 -1
2 3 10 -1
답 31
4
1 2 5 3 9 -1
2 1 5 -1
3 1 9 4 8 -1
4 3 8 -1
답 : 22
6
1 2 3 -1
2 1 3 5 3 3 5 -1
3 2 5 4 7 -1
4 3 7 -1
5 2 3 6 5 -1
6 5 5 -1
답 : 20
4
1 2 7 3 2 -1
2 1 7 -1
3 1 2 4 3 -1
4 3 3 -1
답 : 12
5
1 2 7 3 2 5 10 -1
2 1 7 -1
3 1 2 4 3 -1
4 3 3 -1
5 1 10 -1
답 : 17

 

특이사항

 처음에는 각 정점에 대해서 DFS를 수행했더니 메모리 초과에 걸렸다. DFS를 진행하면서 이미 탐사를 완료한 정점에 대해서는 그 정점에서의 최대거리를 반환하는 방식으로 했는데도 메모리 초과를 피할 수 없었다.