[BaekJoon/백준] 1167번 C++

어려웠다.

 

bfs로 풀어나가긴 했는데

그게 전부가 아니였다.

 

일단 bfs의 depth 개념을 이용하는 문제이긴 한데,

depth 그 자체는 아니고, 간선마다 길이가 다르므로 그 값을 이용해줘야한다.

 

전체적인 풀이계획. 가정은 임의의 경우를 말한 것.

처음에는 모든 노드에서 bfs를 구하여 코드를 만들었다. 당연히 상식적인 선에서 이렇게 구현하면 문제가 풀렸다.

예제들도 다 들어맞길래 정답인 줄 알았는데.. 시간초과가 떴다. 문제는 모든 노드에서 bfs를 해줬던 것이였다.

 

알아보니, 트리의 지름을 구할 때엔 각각의 노드마다 bfs를 전부 시도할 필요는 없고 단 두번으로 해결된다고 한다.

왜 두번인지 더 알아봤는데도, 왜 두번인지 모르겠다.

 

설명에서는, 임의의 노드에서 가장 큰 가중치를 가진 노드를 찾은 뒤에 (간선의 길이를 포함하여 가장 멀리 떨어진 노드)

그 노드에서 다시 큰 가중치를 가진 노드를 찾으면, 전체를 돌 필요 없이 단 두번만으로도 문제가 해결될 수 있다고 한다.

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

using namespace std;


vector<pair<int, int>> v[100001];
queue<int> q;
int visit[100001];
int z[100001]; // depth 계산. 노드 마다 연결된 길이가 다르므로 이를 이용해서 값을 구해야 한다.
int N;

int input, temp, length;

int far; // 임의의 노드에서 가장 큰 가중치를 가진 노드를 찾기 위해 사용.


int bfs(int start) {
    
    int MAX = 0;
    
    q.push(start);
    visit[start] = 1;
    
    while(!q.empty()) {
        
        int tmp = q.front();
        q.pop();
        
        for(int i = 0; i < v[tmp].size(); i++) {
            int n = v[tmp][i].first; // 노드
            int l = v[tmp][i].second; // 길이
            
            if(visit[n] == 0) {
                q.push(n);
                visit[n] = 1;
                z[n] = z[tmp] + l;
                
                // start에서 시작되는 최대 길이 = MAX
                if(MAX <z[n]) {
                    MAX = z[n];
                    far = n;
                }
                
            }
        }
        
    }
    
    return MAX;
    
}

int main() {
        
    int result = 0;
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        cin >> input;
        
        while(1) {
            cin >> temp;
            if(temp == -1)
                break;
            cin >> length;
            
            v[input].push_back({temp, length});
//            v[temp].push_back({input, length}); 문제에서 이중 연결의 경우를 알아서 완벽하게 줌.
            
        }
    }
    
//    for(int i = 1; i <= N; i++) {
//        memset(visit, 0, sizeof(visit));
//        memset(z, 0, sizeof(z));
//        int b = bfs(i);
//        if(result < b)
//            result = b;
//    }
    
    result = bfs(1);
    memset(visit, 0, sizeof(visit));
    memset(z, 0, sizeof(z));
    result = bfs(far); // 덮어씀.

    cout << result;
}

 

 

참고자료

https://www.acmicpc.net/board/view/60904

https://mygumi.tistory.com/226