문제

1167번 문제 링크

1967번 문제 링크

결과

일단 기분 좋은 결과부터 보고 가자 ㅎㅎ

사진

트리의 이해

  • 트리는 방향이 있는 그래프가 아니고 사이클이 존재하지 않는다.
  • 때문에 더 짧은 길이 들어와서 길의 크기를 업데이트 해줄 일이 없다.(다른 길이 있다는 건 사이클이 존재한다는 것이다.)
  • 엣지가 하나밖에 없는 노드는 leaf나 root 노드가 될 수 있고 이러한 노드들을 root node로 정해서 찾은 길 중에 최장거리가 있다.

어떻게 접근할 것인가

  • edge가 하나인 vertex를 모두 거리 찾는 함수에 보내준다.
  • 거리 찾는 함수 내부에서는 BFS로 각 노드의 거리를 업데이트 시켜준다.
  • 그 중 가장 긴 노드를 보내주면 된다.

백준님의 힌트

임의의 점에서 가장 먼 노드(A)를 찾고 그 노드(A)에서 가장 먼 노드까지의 거리가 트리의 지름입니다.

  • 만일 임의의 A라는 노드에서 가장 멀리있는 노드가 D라고 하자.
  • A라는 노드에서 가장 멀리 있는 노드를 D는 그럼 root 노드가 될 수 있다.
  • root node에서 부터 시작해서 가장 멀리 있는 노드는 leaf 노드 중에 거리가 가장 긴 것일 것이다.

코드(1167번)

#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdio>
#define INF 1000000000

using namespace std;

typedef struct Point{
    int v, w;
    Point(){}
    Point(int i, int j){
        v = i;
        w = j;
    }
}Point;

queue<int> q;
vector< vector< Point > > ll;
int n, v, w, u;

char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}

Point find_d(int root){
    int max_i = 1;
    vector<int> d(n+1, INF);
    queue<int> q;
    d[root] = 0; 
    q.push(root);
    while(!q.empty()){
        u = q.front(); q.pop();
        for(int i = 0; i < ll[u].size(); i++){
            v = ll[u][i].v, w = ll[u][i].w;
            if(d[v] != INF)continue;
            d[v] = d[u] + w;
            q.push(v);
        }
    }
    for(int i = 1; i < d.size(); i++){
        if(d[max_i] < d[i])max_i = i;
    }
    return Point(max_i, d[max_i]);
}


int main(){
    n = readInt();
    ll = vector< vector< Point > >(n+1);
    for(int i = 0; i < n; i++){
        int n1, n2, w;
        n1 = readInt();
        while(1){
            n2 = readInt();
            if(n2 == -1) break;
            w = readInt();
            ll[n1].push_back(Point(n2,w));
        }
    }
    printf("%d", find_d(find_d(1).v).w);
}

느낀점

  • 세상에 드디어 구현했다.. 일주일 넘는 시간 동안 방치했던 문제였는데 최단 거리 문제를 풀고 이문제를 보니 문제를 보는 시야가 조금 달라졌다.
  • 트리에 대해서 잘 공부할 수 있었던 것이 너무 좋았다.
  • 내가 제일 힘들게 풀었던 문제에서 3등이라니 너무 기분 좋다…!
  • 다음에도 더 잘 풀어보자아아~!!