[C++] 1167번 트리의 지름 - 그래프 이론, BFS

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

using namespace std;

vector<vector<pair<int, int>>> v;
vector<bool> visit;  //방문했던 노드
int T, p, dis;  //정점의 개수 T, 최대 지점 노드, 거리

void dfs(int node, int cnt)
{
    if(visit[node])
        return;
    visit[node]=1;  //갔다 온 곳은 메모하기
    for(auto k : v[node])
        dfs(k.first, cnt+k.second);  //다음 노드와 총 거리 넣어주기
    if(dis < cnt) {
        dis = cnt;
        p = node;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(NULL); cin.tie(NULL);
    
    int n, k, a, b;
    
    cin >> T;
    v.resize(T+1);
    for(int i=0; i<T; i++) {
        cin >> k >> a;
        while(a!=-1) {
            cin >> b;
            v[k].push_back({a, b});
            cin >> a;
        }
    }
    
    visit.resize(T+1, 0);
    dfs(1, 0);
    fill(visit.begin(), visit.end(), 0);
    dis=0;
    dfs(p, 0);
    
    cout << dis;
}

그래프를 어떻게 구현해야 할지 처음에 몰라서 많이 고민했다. 물론 다른 블로그를 보고 간신히 풀 수 있었다. 아마 이 문제를 풀면서 제일 이해가 안됬던 부분은 이진 트리인지 아닌지였다. 알고보니 이 문제는 딱히 트리를 구현해서 푸는 문제는 아닌 듯 하다. 뭐, 어찌됬던...

 

 

<C++ push_back()>

https://shaeod.tistory.com/574

[C++ STL] std::vector - push_back

 

<C++ fill()>

https://twpower.github.io/121-usage-of-fill-function

[C++] fill 함수 사용하기

 

<C++ vector의 크기 .size>

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=hbom20&logNo=221364679628 

[C++] vector의 크기 :: sizeof 와 .size()

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.