[백준][C++]1167번 트리의 지름

문제

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

1167번: 트리의 지름

 

 

풀이

가장 긴 경로 찾기 ⇒ 임의의 노드에서 가장 긴 경로로 연결된 노드는 트리의 지름에 해당하는 두 노드 중 하나다.

1. 그래프를 인접 리스트로 저장한다.
2. 임의의 노드에서 탐색을 수행하고 탐색할 때 각 노드의 거리를 배열에 저장한다.
3. 2번에서 얻은 배열에서 임의의 노드와 가장 먼 노드를 찾는다.
4. 3번에서 찾은 노드부터 탐색을 다시 수행하고 탐색할 때 각 노드의 거리를 배열에 저장한다.
5. 4번에서 거리 배열에 저장한 값 중 가장 큰 값을 이 트리의 지름으로 출력한다.

 

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

typedef pair<int, int> node;

void DFS(int n);
static vector<vector<node>> graph;
static vector<int> lens;
static vector<bool> visited;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int V;
  cin >> V;
  
  graph.resize(V + 1);	// 인접 리스트 graph 크기 초기화
  lens.resize(V + 1);
  visited.resize(V + 1);
  int now, next, len;
  for(int i = 0; i < V; i++)
  {
    cin >> now;

    while(true)
    {
      cin >> next;
      if(next == -1)
      {
        break;
      }
      cin >> len;
      
      graph[now].push_back(make_pair(next, len));	// 인접 리스트 graph에 그래프 데이터 저장
    }
  }

  fill(lens.begin(), lens.end(), 0);	// 거리 배열 초기화
  fill(visited.begin(), visited.end(), false);	// 방문 배열 초기화
  DFS(1);

  int max_num = 0, max_index = 0;
  for(int i = 1; i <= V; i++)
  {
    if(max_num < lens[i])
    {
      max_num = lens[i];
      max_index = i;
    }
  }
  
  fill(lens.begin(), lens.end(), 0);	// 거리 배열 초기화
  fill(visited.begin(), visited.end(), false);	// 방문 배열 초기화
  DFS(max_index);	// 거리 배열에서 가장 큰 값을 다시 시작점으로 지정

  // lens 배열에서 가장 큰 수를 정답으로 출력
  max_num = 0;
  for(int i = 1; i <= V; i++)
  {
    if(max_num < lens[i])
    {
      max_num = lens[i];
    }
  }
   
  cout << max_num;
  
  return 0;
}

// DFS 구현
void DFS(int n)
{
  visited[n] = true;	// visited 배열에 현재 노드 방문 기록

  for(node next : graph[n])
  {
    int node = next.first;
    int len = next.second;

    if(!visited[node])	// 현재 노드의 연결 노드 중 방문하지 않은 노드에 대해
    {
      lens[node] = lens[n] + len;	// 거리 배열 업데이트
      DFS(node);
    }
  }
}

 

 

오답

• 트리의 지름 구하기 ⇒ 두 번의 탐색를 수행해야한다. (임의의 노드 → 임의의 노드와 가장 먼 노드)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> edge;
static vector<vector<edge>> A;
static vector<bool> visited;
static vector<int> m_distance;
void BFS(int node);

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;
  A.resize(N + 1);

  for(int i = 0; i < N; i++)
  {
    int S;
    cin >> S;
    while(true)
    {
      int E, V;
      cin >> E;
      if(E == -1)
      {
        break;
      }
      cin >> V;
      A[S].push_back(edge(E, V));
    }
  }

  m_distance = vector<int>(N + 1, 0);
  visited = vector<bool>(N + 1, false);
  BFS(1);
  int Max = 1;

  for(int i = 2; i <= N; i++)
  {
    if(m_distance[Max] < m_distance[i])
    {
      Max = i;
    }
  }
  fill(m_distance.begin(), m_distance.end(), 0);  // 거리 배열 초기화
  fill(visited.begin(), visited.end(), false);  // 방문 배열 초기화
  BFS(Max);  // 거리 배열에서 가장 큰 값을 다시 시작점으로 설정
  sort(m_distance.begin(), m_distance.end());
  cout << m_distance[N] << "\n";
}

// BFS 구현
void BFS(int index)
{
  queue<int> myqueue;
  myqueue.push(index);
  visited[index] = true;

  while(!myqueue.empty())
  {
    int now_node = myqueue.front();
    myqueue.pop();
    for(edge i : A[now_node])
    {
      if(!visited[i.first])
      {
        visited[i.first] = true;
        myqueue.push(i.first);
        // 거리 배열 업데이트
        m_distance[i.first] = m_distance[now_node] + i.second;
      }
    }
  }
}