글 읽기 - 시간초과 해결을 못하겠습니다.

joseph415 5년 전 0

시간초과가 계속 떠서 질문검색해서 확인해보니 초기화를 계속해줄필요가 없다 하셔서 check라는 배열을 따로 만들어서

싸이클이 형성되었으면 체크를 해서 더이상 dfs를 실행하지 않게 만들었는데 시간초과가 계쏙 뜹니다 ㅠㅠ

어떻게 바꿔야 할까요 ,,,

#include <iostream>
#include <vector>
#define N 100000
using namespace std;
enum state
{UNDISCOVERED,DISCOVERED};

//-------------------------------------
int state[N];
int s = 0;
void init_state(){
    int i;
    for(i=0;i<N;i++)
        state[i]=UNDISCOVERED;
}
int c=0;
void DFS(vector<int> a[],int check[],int start,int v) {
        c++;
        int neighbor;
        state[start] = DISCOVERED;
        for (int i = 0; i < a[start].size(); i++) {
            if(c==1)
                s=start;
            neighbor = a[start][i];
            if (state[neighbor] == UNDISCOVERED) {
                DFS(a,check ,neighbor,v);
            }
            else {
                if (s != neighbor) {
                    c = 0;
                }
                else {
                    for (int j = 0; j < v; j++)
                        if (state[j] != UNDISCOVERED) {
                            check[j] = 1;
                        }
                }
            }
        }
}

int main() {
    int t;
    cin >> t;
    int total[N];
    int v;
    for (int j = 0; j < t; j++) {
        int check[N]={};
        init_state();
        int sum = 0;
        vector<int> a[N];
        scanf("%d", &v);
        for (int i = 0; i < v; i++) {
            int u;
            scanf("%d", &u);
            a[i].push_back(u - 1);
        }
        for (int i = 0; i < v; i++) {
            if(check[i]!=1) {
                DFS(a,check ,i, v);
            }
            sum += c;
            c = 0;
        }
        total[j] =v-sum;

    }
    for (int i = 0; i < t; i++) {
        printf("%d\n", total[i]);
    }
}

evenharder 5년 전 1

코드의 몇몇 부분에 대한 조언을 드리고 싶습니다.

1. 함수 안에서 int check[100000] 등으로 지역변수를 할당하는 것은 일부 환경에서는 불가능할 수 있습니다 (런타임 에러의 가능성이 있습니다). 전역 변수로 선언하시는 걸 권장합니다.

2. vector<int> a[N]은 int a[N]으로 바꾸어도 상관없습니다. (왜일까요?)

3. 시간 초과가 나는 이유는 33번째 줄에 있는 반복문 때문입니다. DFS가 최대 v번 호출될 수 있고 반복문도 복잡도가 O(v)이므로 시간 복잡도가 O(v^2)입니다.

4. state와 check의 역할이 겹칩니다. state에 '이 정점을 몇 번째로 방문했는지'를 넣고 DFS를 이용해보세요. check 없이 state만으로도 문제를 해결할 수 있습니다.

5. 이 코드는 '틀렸습니다'가 나오는 예시도 있습니다. 이는 밑의 코드로 첨부하겠습니다.

Input
1
4
2 3 4 2

Output
1

joseph415 5년 전 0

@evenharder

감사합니다. 드디어 해결했습니다!

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

문제

문제

출처

ICPC

시간초과 해결을 못하겠습니다.

joseph415 5년 전 0

evenharder 5년 전 1

joseph415 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말