[백준,c++] 1595번 - 북쪽나라의 도로

문제

1595번: 북쪽나라의 도로

 

코드

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

vector<pair<int,int>>graph[10001];
bool visited[10001];
int max_cost, max_node;

void dfs(int node, int cost){
    if(cost>max_cost){
        max_cost = cost;
        max_node = node;
    }
    visited[node] = 1;
    for(auto next: graph[node]){
        if(!visited[next.first]){
            dfs(next.first, cost + next.second);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int a, b, c;
    while(cin>>a>>b>>c){
        graph[a].push_back({b,c});  //a에서 b까지 가는데 c만큼의 비용이 든다.
        graph[b].push_back({a,c});
    }
    
    dfs(1,0);
    memset(visited, 0, sizeof(visited));
    max_cost = 0;
    dfs(max_node, 0);
    cout<<max_cost;
}

 

풀이

가장 거리가 먼 두 도시 간의 거리를 출력하는 문제입니다.

노드의 갯수가 최대 10,000 이기 때문에 O(N^2) 복잡도로는 해결할 수 없는 문제입니다.

위 문제는 다음의 문제와 동일합니다.

[백준,c++] 1167번 - 트리의 지름

모든 노드를 탐색할 필요없이 그냥 아무 노드나 기준점으로 잡고 출발해 가장 긴 노드를 찾은 후 해당 노드에서 dfs를 돌리면 O(N+M) 시간 복잡도로 가장 긴 길이를 찾을 수 있습니다.