글 읽기 - 시간 복잡도 질문있습니다.

jaeseb96 4년 전 0

#1 코드는 정답

#2 코드는 시간초과를 받았습니다.

#2 코드는 임의로 벡터 두개로 함수에 넘기면서 정답 받고 수정하려고 짠 코드이긴 한데

매개변수로 벡터를 넘기는 것과 #1 코드처럼 전역으로 bool array에 경로를 체크하는 것이 시간 초과의 당락을 결정 할 정도로 큰 차이의 시간차이를 발생시키나요?

이유가 궁금합니다.

#1

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>

using namespace std;

vector <vector <pair <int, int>>> V;
int N;
int IDX;
int A, B;
int MAX;
int ep; // end point
bool P[100001];

void DFS (int s, int l)
{
    P[s] = 1;

    if (MAX < l) {
        ep = s;
        MAX = l;
    }

    int SIZE = V[s].size();

    for (int i=0; i<SIZE; i++) {
        if (P[V[s][i].first] == 0)
            DFS (V[s][i].first, l+V[s][i].second);
    }
}

int main (void) {
   // freopen ("input2.txt", "r", stdin);

    scanf("%d", &N);

    V.resize(N+1);

    for (int i=0; i<N; i++) {
        scanf("%d ", &IDX);

        while (1) {
            scanf("%d ", &A);

            if (A!=-1)
                scanf("%d ", &B);
            else
                break;

            //printf("%d %d\n", A, B);

            V[IDX].push_back(make_pair(A, B));
        }
    }

    DFS(1, 0);

    memset(P, 0, sizeof(P));
    MAX = 0;
    DFS(ep, 0);

    printf("%d\n", MAX);

    return 0;
}

#2

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector <vector <pair <int, int>>> V;
int N;
int IDX;
int A, B;
int MAX;
int ep; // end point

void DFS (int s, int l, vector <int> P)
{
    P[s] = 1;

    if (MAX < l) {
        ep = s;
        MAX = l;
    }   

    int SIZE = V[s].size();

    for (int i=0; i<SIZE; i++) {
        if (P[V[s][i].first] == 0)
            DFS (V[s][i].first, l+V[s][i].second, P); 
    }   
}

int main (void) {
    //freopen ("input2.txt", "r", stdin);
    
    scanf("%d", &N);

    V.resize(N+1);

    for (int i=0; i<N; i++) {
        scanf("%d ", &IDX);

        while (1) {
            scanf("%d ", &A);

            if (A!=-1)
                scanf("%d ", &B);
            else
                break;

            //printf("%d %d\n", A, B);

            V[IDX].push_back(make_pair(A, B));
        }
    }   


    vector <int> P (N+1);
    DFS(1, 0, P); 

    vector <int> T (N+1);
    MAX = 0;
    DFS(ep, 0, T); 

    printf("%d\n", MAX);

    return 0;
}

kyo20111 4년 전 1

두번째 코드의 DFS 함수의 vector<int> P 부분을 vector<int> &P 로 바꾸는 시간내에 돌아갑니다.

아마도 함수가 실행 될 때마다 P를 복사하기 때문일거에요 (dfs 1번 할때마다 N+1 크기의 vector 생성)

&P로 하면서 복사하지 않고 기존의 값을 사용한다 라고 생각하면 좋을것 같아요

궁금하시면 직접 찾아보시는게 좋을것 같아요.. 저는 지식이 얕아서 자세히는 대답 못해드리네요 ㅜㅜ

jaeseb96 4년 전 0

댓글보고 이곳저곳 찾아보고 실험해보니 말씀하신 것이 맞는 것 같아요 !

그래서 함수 매개변수를 vector <int> &P 로 포인터를 넘겨주는 방식으로 바꾸면 시간초과가 해결되네요

감사합니다

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

문제

문제

출처

ICPC

시간 복잡도 질문있습니다.

jaeseb96 4년 전 0

kyo20111 4년 전 1

jaeseb96 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말