1167) 트리의 지름

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>

//pair클래스 : template <class T1, class T2> struct pair;
//pair <[tpye1], [type2]> p : 사용할 데이터타입 1, 2를 넣고, 그 클래스 p의 생성
//p.first(second) : p의 첫(두)번째 인자 반환
//make_pair(변수1, 변수2) : 변수 1(2)가 들어간 pair의 생성

using namespace std;
#define MAX 100001

vector<pair<int, int>> route[MAX]; 
//<int, int> 형을 담는 pair형 vector, route 선언. 이 때, 벡터 안에는 max만큼 삽입
bool check[MAX];
int distance[MAX];
int answer;

//void fill(ForwardIterator first, ForwardIterator last, constT& val);
//: 채우고자 하는 자료구조 시작위치 first, 끝위치 last, 채우고자하는 값
//(T에 의해객체, 자료형도 가능)

int loop; //몇 번 실행할 것인가?

void Find(int start)
{
fill(check, check + MAX, false); //check라는 자료구조의 처음부터 max까지 FALSE
fill(::distance, ::distance + MAX, 0);
//모호합니다: distance라는 클래스 따로 존재. std::(기존 std상) vs ::(내가 선언)

queue<int> q;

check[start] = true; //1, 즉 시작점을 true
q.push(start);

while (!q.empty())
{
int node = q.front(); //node는 q의 첫번째. 저장.
q.pop(); //node에 따로 저장 후, q를 pop
// printf("node %d size %d\n", node, route[node].size());

for (int p = 0; p < route[node].size(); p++) //route의 사이즈만큼
//vector<pair<int, int>> route[MAX]: route라는 벡터가 max개 있다.
//이 배열 1개 [n]에는, 따라서 하나의 pair<int, int> 벡터가 있다.
//벡터는 배열의 일종이며, input을 통해 route[n]에 pair을 -1이 될때까지 삽입
//따라서, 현재 route[n]에는 cost로 연결된 to의 정점 개수만큼의 사이즈가 있다
//일일이 이 route[node]에 연결된 정점들을 검사
{
int next_node = route[node][p].first;
// printf("next node %d \n", next_node);
//route[node][p].first= route 벡터배열 내 [node]번째의 p번째 pair의 첫요소
if (check[next_node] == false)
//만일 이것이 아직 도달하지 않은 곳일때
{
::distance[next_node] = ::distance[node] + route[node][p].second;
q.push(next_node);
check[next_node] = true;
//다익스트라의 응용. node와 연결된 q 정점이 차례로 push된다.
}
}
}
}

void input()
{
cin >> loop; //cin = scanf

for (int i = 0; i < loop; i++)
{
int from;
cin >> from;

int to = 0; int cost = 0;
while (true)
{
cin >> to; if (to == -1) break;
cin >> cost;

route[from].push_back(make_pair(to, cost));
}
}
}

int main()
{
input();
Find(1);

int start = 1;
for (int i = 2; i <= loop; i++)
{
if (::distance[i] > ::distance[start])
start = i;
}

Find(start);
int answer = ::distance[1];

for (int i = 2; i <= loop; i++)
{
if (answer < ::distance[i])
answer = ::distance[i];
}

cout << answer << "\n";

system("pause");
return 0;
}

////////////////////////////////////////////////

c++ 형식의 자료구조를 익히기 위해 완전히 남의 것을 베낀 후

분석해가며 주석을 달았다. 

이걸 분석하면서 뭔가 알고리즘이 맞지 않는다는 생각을 했다. 왜냐하면 그래프 상에서는 정답이 아니기 때문이다.

 

근데 생각해보니 트리더라... 트리는 bfs형식으로 한 번 진입해서 방문에 true를 매기면, 다시 거기를 살필 필요가 없다.

왜냐하면 상하구조 트리에서, 여기에 접근했다는 뜻은 부모 노드에서 진입했다는 뜻이니까.

그래프에서는, 다른 노드를 들렀다가 위의 노드로 더 효과적으로 진입할 수 있다면 다시 가야 하지만, 트리는 그럴 필요가 없다. 상하 구조에서, 아래에서 위로 가니 더 가까워 지더라... 라는 일은 상정할 필요가 없기 때문이다.

 

괜히 그래프라 생각하고 헛돌았다....

따라서, bfs에서 한 번 들르면 바로 true 처리를 하는 것이다.

이를 토대로, 한 번 1 노드에서 가장 먼 곳을 찾은 다음, 여기에서 가장 먼 곳을 찾으면 된다.