[5주차_수요일] 트리의 지름

[yeongleej]

• 사이트 : 백준(BOJ)
• 문제: 트리의 지름
• 번호: 1967

[KodaHye]

🤔 시간복잡도 고려사항

• 1<= 노드의 개수 <= 10,000
• 간선의 개수 n - 1, 양방향 그래프로 구현 → 2n - 2
• 간선리스트로 노드의 정보를 저장하고 2번의 bfs를 통해 트리의 길이 구하기
  • 인접리스트일 때 BFS 시간복잡도: O(N + E) (N: 정점, E: 간선)
  • 2 × (10,000 + (2 × 10,000 - 1)) < 1억

💡 풀이 아이디어

트리의 길이 = (한 지점에서 가장 멀리 떨어져 있는 지점)에서 또 다시 그 지점에서 가장 멀리 떨어져 있는 지점

• maxInfo[]
  • maxInfo[0]: 가장 멀리 떨어져 있는 Node의 idx 저장
  • maxInfo[1]: 가장 멀리 떨어져 있는 Node가 start 지점으로부터 얼마나 떨어져있는지 저장
• int[] getMaxDisInfo(int start): start 지점으로부터 가장 멀리 떨어져있는 노드의 정보 구하기
  1. 루트 노드를 기준으로 가장 멀리 떨어져 있는 노드 정보 구하기
  2. 1의 결과를 통해 얻은 노드 기준으로 가장 멀리 떨어져 있는 노드 정보 구하기

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 10,000 → 10^4이므로 O(n^2) 가능

💡 풀이 아이디어

• 한 리프 노드에서 다른 리프 노드까지의 가중치 합의 최대치를 구하는 문제
• 모든 리프 노드를 순회하는 것은 비 효율적 → 그리디하게 풀자, 하나의 노드를 선택
  • 루트로부터 가장 멀리 떨어져 있는 리프 노드를 시작 노드로 선택하면 최적의 해
• 선택한 리프 노드에서 다른 리프 노드까지의 가중치 합의 최대치를 구해주고 출력

  // 루트로부터 가장 멀리 떨어져 있는 리프 노드 찾기
  visited = new boolean[n + 1];
  dfs(1, 0);
  // 선택된 리프 노드에서 다른 리프노드까지의 최대 가중치를 찾기
  visited = new boolean[n + 1];
  dfs(maxNode, 0);

  모든 리프 노드에서 값을 계산해줬는데 1500ms 나와서 그리디하게 바꿨습니다..

[yeongleej]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 10,000
• dfs 탐색 => O(N^2) 가능

💡 풀이 아이디어

• 트리의 특징

  • 사이클이 없는 하나의 연결 그래프 ⇒ 즉, 모든 노드가 하나로 연결됨

• 트리의 특징에 따라 임의의 노드에서 가장 먼 노드를 찾고, 그 노드에서 다시 먼 노드를 찾으면 트리의 지름을 구할 수 있다.

  • 즉, 2번의 dfs 탐색 진행

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 10,000
• 10^4 → O(n^2) 가능

💡 풀이 아이디어

• 가장 긴 지름

  1. 특정 노드(root)로부터 가장 먼 노드(tmpNode)
  2. tmpNode로부터 가장 먼 노드 구하기

• dfs를 통해 시작노드a로부터 가장 먼 노드b구하기 2번 반복

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: DFS
• 시간복잡도: 1 ≤ n ≤ 10,000 10,000 x 10,000 = 1억으로 O(n^2) 까지 가능

💡 풀이 아이디어

• 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이 구하기

  • DFS 2번 탐색하기
  • 1번: 루트에서 가장 멀리 있는 노드 탐색 (루트는 항상 존재하기 때문에 루트에서 시작)
  • 2번: 해당 노드에서 가장 먼 노드 탐색 > 가장 긴 길이 계산

• 최소신장트리 불가한 이유 이미 주어진 트리는 최소 간선으로 연결되어 있기 때문에 union&find 진행할 필요없음

• BFS 불가한 이유 BFS는 각 간선의 가중치를 고려하지 않고 단순히 레벨을 따라 탐색하기 때문에 간선의 가중치가 모두 다르므로 가장 큰 가중치 값을 구할 수 없음

처음에 문제를 보고 최소신장트리 인줄 알았는데, DFS 문제였군요! 양방향으로 탐색하는 새로운 탐색 방법을 알게 됐어요

[icegosimperson]

🤔 시간복잡도 고려사항 n<=10,000 O(N^2)까지 가능

💡 풀이 아이디어 트리의지름(트리의 모든 경로 중 가장 긴 경로) -> DFS로 탐색 임의의 노드에서 가장 먼 노드 찾기 -> 첫번째 DFS 수행 -> 두번째 DFS 수행 -> 트리의 지름