글 읽기 - 1967 시간초과요.

yujjjang 6년 전 0

시간초과가 떠요 한 36%정도에서 뜹니다.

너무나 비효율적으로 짠거같아서 창피하지만 개선방안을 알려주셨으면 좋겠습니다.

어느부분의 시간을 단축하여야 할까요.. 감사합니다. !

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

using namespace std;
//노드. 자식들까지의 거리와 그 노드포인터를 저장.
class Node{
  private:
    int data;
    vector<Node*> Child;
    vector<int> Distance;
  public:
    Node(){
      data = 0;
      Child.clear();
      Distance.clear();
    }
    void setData(int data){
      this -> data = data;
    }
    void setNode (Node* child, int distance) {
      Child.push_back(child);
      Distance.push_back(distance);
    }
    int getData(){ return data; }
    vector<Node*>& getChild() { return Child; }
    vector<int>& getDistance() { return Distance; }
};

class Tree{
  private:
    Node* root;
    vector<int> sd;
  public:
    Tree(){};
    int getDistance(Node* root);
    int getChildDistance(Node* Child, int distance);
    void Sort(int left, int right);
};
//하나의 루트로 부터 얻을수 있는 길이(자식들의 것) 중 큰거 2개를 선택해 그 값을 리턴함.
int Tree::getDistance(Node* root) {
  sd.clear();
  vector<Node*> tmp = root->getChild();
  vector<int> dis = root->getDistance();
  int kk;
  if (tmp.size() == 0) return 0;
  for (int i = 0; i < tmp.size(); ++i)
    sd.push_back(getChildDistance(tmp[i], dis[i]));
  int idx = sd.size();
  sort(sd.begin(), sd.end());

  int sum = sd[idx-1] + sd[idx-2];
  return sum;
}
// 길이구하는거 (재귀)
int Tree::getChildDistance(Node* Child, int distance) {
  vector<Node*> tmp = Child->getChild();
  vector<int> dis = Child->getDistance();

  if(tmp.size() == 0) return distance; // 종료조건 . 더이상 자식이 없으면 그때 까지의 거리를 리턴.
  int sum = 0;
  int kkk = 0;

  for (int i = 0; i < tmp.size(); ++i){
    sum = getChildDistance(tmp[i], dis[i] + distance);
    kkk = (sum > kkk) ? sum : kkk;
  }
  return kkk;
}

int main(){
  int num;
  cin >> num;
  Node node[num];
  for (int i = 0; i < num; ++i){
    node[i].setData(i+1);
  }
  int cnt = 0;
  int ans = 0;
  int tmp = num;
  int parent;
  int child;
  int distance;

  num -= 1;

  while(num--){
    cin >> parent;
    cin >> child;
    cin >> distance;

    node[parent-1].setNode(&node[child-1], distance);
  }
  Tree tree;
    // 모든 노드를 루트로 하여서 가장 큰값 출력.
  for (int i = 0; i < tmp; ++i) {
    cnt = tree.getDistance(&node[i]);
    if (cnt > ans) ans = cnt;
  }
  cout << ans << endl;
  return 0;
}

sgchoi5 6년 전 2

아래 koosaga 님이 작성하신 글을 추천합니다요..

http://koosaga.myungwoo.kr/ent...
// 아무 점이나 잡고(루트), 이 점에서 가장 거리가 먼 점 t 를 잡는다
// t에서 가장 거리가 먼점 u 를 찾는다
// 트리의 지름 = t -> u

yujjjang 6년 전 0

감사합니다.

저 내용을 이해하려고 하다 답글다는게 늦었습니다. 죄송합니다.

좋은 정보 감사합니다. 정말 엄청난 생각인것 같습니다... 봐도 이해하는데 까지 시간이 오래걸렸네요 ㅠㅠ

감사합니다 !!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1967 시간초과요.

yujjjang 6년 전 0

sgchoi5 6년 전 2

yujjjang 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말