[C/C++] 백준 1167: 트리의 지름 (다익스트라 풀이)

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

1167: 트리의 지름

풀이 방법??

 문제 자체가 트리의 지름을 구하라고 하는데 이때 트리의 지름이란 임의의 두 점 사이의 거리 중 가장 긴 것을 의미한다. 그렇기 때문에 모든 노드에서 DFS 혹은 다익스트라 알고리즘을 통해 가장 긴 거리를 구하려는 것이 첫번째 생각일 것이다. 하지만 이렇게 할 경우 각 정점마다 (V) 트리를 모두 순회하며 (V) 최댓값을 구해야하기 때문에 O(V^2)의 시간이 걸려 시간제한에 걸릴 것이다.

 

 그렇기 때문에 익히 알려져있는 기법을 사용하여 이 문제를 풀어야한다. 바로 "임의의 한 노드에서 가장 멀리 떨어진 노드가 트리의 지름 중 한 곳"이라는 것인데 직관적으로 원을 떠올리고 좌표상에서 생각해보면 이해하기 쉬울 것이다. 이후 지름 중 한 곳에서 똑같이 가장 멀리 떨어진 노드를 찾으면 그곳이 또 다른 지름중 한 곳이 되어 이 두 노드 사이의 거리가 곧 트리의 지름이 된다.

 

 이 거리는 DFS나 다익스트라 알고리즘으로 쉽게 구할 수 있다. 사실 DFS로 푸는 것이 구현하는데 더 쉬울 수 있지만 최근에 다익스트라 알고리즘을 공부하고 있던 입장에서 한번 다익스트라 알고리즘으로 풀어보았다!

 

 

다익스트라의 변형

 다익스트라 알고리즘은 그래프에서 단일 지점에서 임의의 한 지점까지의 "최단거리"를 구하는 알고리즘이다. 하지만 이 문제에서는 최장거리를 원하고 있으므로 코드의 변형이 필요했다! 기존의 다익스트라 구현과정은 아래 포스팅에 잘 정리해두었으니 참고하면 도움이 될 것이다!!!!

https://donggul-godsang.tistory.com/77

[C/C++] 백준 1916: 최소비용 구하기 (다익스트라 구현하기!)

 

1. dist 백터의 초기화

 dist 백터는 시작점에서 원하는 지점까지의 최장거리를 저장하는 백터이다. 다만 기존 다익스트라 알고리즘에서는 dist(V+1,INT_MAX)로 최단거리를 업데이트하기 위해 INF로 초기화 해두었지만 이 문제에서는 최장거리를 업데이트 해야하기 때문에 간선들의 합이 0미만으로 내려가지는 않으므로 

 

vector<int>dist(V+1,-10000);

 

로 초기화했다!

 

2. 최장거리 continue 및 업데이트

 물론 이 문제는 트리로 주어진 그래프이기 때문에 한 노드까지 가는 경우가 여러가지가 아닐 수도 있다. 그리고 이진 트리라면 필요없는 반복문이지만 나중에 확장했을 때 사용하기 위해 넣어주었다. 기존 다익스트라 알고리즘에서는 매우 중요한 역할을 하는 조건문인데 기존 알고리즘에서는 임의 노드까지 가는 최단거리보다 큰 거리가 cur_dist로 올 경우 이 경우는 무시하고 그 다음 queue.top을 확인하기 위해 

 

if(dist[cur_V]<cur_dist) continue; 

로 선언했었다.

 

하지만 이번에는 더 작은 거리가 cur_dist로 올 경우 이 경우는 무시하기 위해서

 

if(dist[cur_V]>cur_dist)  continue;

으로 선언하였다.

 

마찬가지로 dist 백터를 업데이트하기 위한 조건문 역시

if(dist[tmp]<next_dist) //더 긴 경로를 발견하면 인접한 노드까지의 최장거리를 갱신
        {
          dist[tmp]=next_dist;
          q1.push(make_pair(next_dist,tmp)); //기존 다익스트라와는 다르게 가장 긴 값부터 나오게 처리
        }

이런 식으로 처리를 해주었다.

 

결국 이렇게 만들어진 다익스트라 알고리즘을 2번 사용하여 첫번째에는 가장 먼 지점의 index를 알아내고 두번째에는 트리의 지름을 구하게 된다면 문제가 쉽게 풀리게 된다!!

 

 

 

소스코드!!

 

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

int V;
vector<pair<int,int>> adj_list[100001];
priority_queue<pair<int,int>> q1;
vector<int> result;
int visit_V[100001];

int dijkstra(int start,int*max)
{  
  vector<int>dist(V+1,-10000); //시작점에서 원하는 지점까지의 최장거리를 저장
  dist[start]=0;
  
  q1.push(make_pair(0,start));
  while(!q1.empty())
    {
      int cur_dist=q1.top().first;
      int cur_V=q1.top().second;
      q1.pop();
      if(dist[cur_V]>cur_dist &&visit_V[cur_V]==1)
        continue;
      visit_V[cur_V]=1;

      for(int i=0;i<adj_list[cur_V].size();i++){
        int tmp=adj_list[cur_V][i].first; //인접한 노드의 정점
        if(visit_V[tmp]==1)
          continue;
        int next_dist=cur_dist+adj_list[cur_V][i].second; //첫 노드에서 인접한 노드까지의 거리
        if(dist[tmp]<next_dist) //더 긴 경로를 발견하면 인접한 노드까지의 최장거리를 갱신
        {
          dist[tmp]=next_dist;
          q1.push(make_pair(next_dist,tmp)); //기존 다익스트라와는 다르게 가장 긴 값부터 나오게 처리
        }
      }
    }
    
  int index=0;
  for(int i=1;i<=V;i++)
    {
      if(dist[i]>*max)
      {
        *max=dist[i];
        index=i;
      }        
    }
  return index;
}


int main() {
   ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin>>V;
  for(int i=0;i<V;i++)
    {
      int start,tmp1,tmp2;
      cin>>start;
      while(1){
        cin>>tmp1;
        if(tmp1==-1)
          break;
        cin>>tmp2;
        adj_list[start].push_back(make_pair(tmp1,tmp2));
        }      
    }
  
    int max=0;
    int index=dijkstra(1,&max);     
    memset(visit_V,0,100001*sizeof(int));
    max=0;
    int k=dijkstra(index,&max);    
    cout<<max;
}