글 읽기 - 시간초과 미치겠습니다 ㅠㅠ

psj1028 5년 전 0

후.. 이틀에 걸쳐서 코드를 뒤엎고 완벽하게 코드를 짰다고 생각했는데 시간초과가 발생했습니다. 제가 제출한 코드이고 약81-82%에서 시간초과가 발생했습니다. 이전에도 계속 시간 초과가 발생하여 원인이 무엇일지 곰곰히 생각을 해봤는데 이미 사이클에 포함된 요소를 탐색하는 경우에 시간 낭비가 발생하는 것 같습니다 . 그래서 중복을 방지하도록 cycle[] 을 선언했고 아래 코드와 같이 활용했습니다. 이 코드에서 어떻게 더 줄일 수 있을까요? ㅠㅠ 도저히 방법이 나오지 않습니다.

#include <iostream>
using namespace std;
int a[100001];
int check[100001];
int cycle[100001];
int dfs(int node, int cnt, int start) {
    if (cycle[node] == 1){   
        return 0;
    }
    check[node] = start;
    int next = a[node];
    if (check[next] != start) {
        cnt = dfs(next, cnt + 1, start);
    }
    else if (check[next] == start && a[node] == start && cycle[node] == 0) {
        int k = start;
        //사이클의 노드에 이미 사이클임을 확인했음을 표시하기 위한 코드
        while (cycle[k] == 0) {
            cycle[k] = 1;
            k = a[k];   
        }
        return cnt;
    }
    else {
        return 0;
    }
    return cnt;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        int cnt = 1;
        int ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            check[i] = cycle[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            ans += dfs(i, 1, i);
        }
        printf("%d\n", n - ans);
    }
    return 0;
}

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

문제

문제

출처

ICPC

시간초과 미치겠습니다 ㅠㅠ

psj1028 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말