백준 1167. 트리의 지름 [실패]

# 제목 

1.실패 원인

제일 멍청했던 점은 node -> node,dist 관계를 단순 vector 배열로 풀려했던 것.. pair를 쓰던 구조체를 쓰던.. 거리와 노드를 동시에 기록해야하는데 ㅜ 단순 vector 배열은 할당하기 전까지 특정 메모리에 접근이 불가능하고 문제 조건의 100001 이하의 원소들에 대해 거리를 지정하려면 100001*100001 사이즈를 할당해야하니 말이 안된다.. 이렇게 간단한 것 때문에 시작부터 헤맸다..

 

두 번째는 해당 문제를 dfs로 풀어야 하나 bfs로 풀어야 하나에 대한 것이었는데, 풀이들을 보면 둘 다 가능한 것 같다. 일단 지름은 노드간 거리가 가장 긴 것인데 dfs로 생각하면 분기가 생겼을 때도 하나의 경로에 대해서 끝까지 탐색이 완료된 후 분기점으로 돌아가서 다른 경로를 파기 때문에 하나의 탐색 경로에 대한 길이를 알 수 있다. 따라서 최대 거리를 계속 저장해두고 조건으로 최대거리보다 클 때마다 값을 변경해주면 된다.

 

그리고, 백준 문제 댓글에도 나와 같은 의문을 가지신 분들이 질문을 해주셨는데, 시작 노드를 어떻게 잡아야 하냐는 것이었다. 결론부터 말하면 어떤 노드가 시작점이되든 상관없다. 트릭인지 공식인지.. 노드의 지름을 구하는 방식은 아무 점에서 시작해서 가장 먼 점을 찾고 그 점으로 부터 가장 먼점 사이의 거리가 지름이라는 것이다. 다른 곳에서도 응용될 수 있으니 외워두는게 좋을 것 같다.

 

한 가지 당연하지만 조심해야할 점은 dfs를 2번을 돌게 될텐데 (아무점->가장 먼 점 , 가장 먼 점 -> 가장 먼 점2) visit가 true가 된걸 다시 false로 되돌려 놓아야한다. 즉, 첫 번째 dfs에서 들고 나와야 하는 변수는 가장 먼 점과 해당 노드까지의 최장 거리뿐이다. 가장 먼 점은 위에서 말했듯이 그 점을 시작으로 다시 가장 먼 점을 구해야하기 때문고 최장 거리는 출력을 위해서다.

 

2.작성 코드

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100000 + 1;

 

int V;

bool visited[MAX];

vector<pair<int, int>> graph[MAX];

 

int diameter = 0;

int farthestNode = 0;

 

void DFS(int node, int cost)

{

        //기저 사례: 이미 방문한 곳

        if (visited[node])

                 return;

 

        visited[node] = true;

 

        //지름 업데이트

        if (diameter < cost)

        {

                 diameter = cost;

                 farthestNode = node;

        }

       

        for (int i = 0; i < graph[node].size(); i++)

                 DFS(graph[node][i].first, cost + graph[node][i].second);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> V;

 

        for (int i = 0; i < V; i++)

        {

                 int node;

                 cin >> node;

 

                 while (1)

                 {

                         int node2, cost;

                         cin >> node2;

                         if (node2 == -1)

                                 break;

 

                         cin >> cost;

                         graph[node].push_back({ node2, cost });

                 }

        }

 

        memset(visited, false, sizeof(visited));

        //루트에서 가장 먼 정점 찾고

        DFS(1, 0);

        //해당 정점에서 가장 먼 정점까지의 거리가 트리 지름의 정해

        memset(visited, false, sizeof(visited));

        diameter = 0;

        DFS(farthestNode, 0);

 

        cout << diameter << "\n";

        return 0;

}



//출처: https://jaimemin.tistory.com/812 [꾸준함]

3.참고 코드

https://jaimemin.tistory.com/812

백준 1167번 트리의 지름

 

4. 해결 방안

새로운 개념인 트리의 지름을 알게됐다. 차라리 모르는 개념이 있었기에 틀린 것이 낫다.

그리고, 그래프 문제풀 때 몇가지 개념을 다시 정리해야 할듯하다.

1. dfs -> 연결요소 관련 문제

2. bfs -> 최단 거리

3. 거리 문제에는 vector<pair<int,int>> v[max] (node2,length 담기위한 pair)

4. 트리 지름은 두 번의 dfs를 통해(bfs도 가능) 구할 수 있다.

5. dfs는 한 경로를 먼저 탐색한다.(최적 경로를 알 수 있다.) bfs는 같은 depth로 탐색한다.(가장 먼저 끝나는 녀석이 최단거리이다.)