글 읽기 - c++ 9466 시간 초과

hena_42 2년 전 0

답변 달아주시는 모든 분들께 항상 감사드립니다.

시간 복잡도 계산을 열심히 해보았는데, 잘 할줄 모르는 것 같습니다. 코드가 잘못된 것 이겠지만, 어디가 잘못되었는지 못찾아서 도움이 필요합니다.

1-3-4-1 이런 사이클이라면 1,3,4를 사이클 처리해서 3과 4차례일때는 아예 보지 않는 식으로 짜면 O(n)에 될거라 생각했는데, 실패하였습니다.

#include <bits/stdc++.h>
using namespace std;
int graph[100001];
bool visited[100001];
bool cycle[100001];
int n;
void depth_first_search(int start, int end, vector<int> &v)
{
    // 사이클인 값이었다면 무시하고 리턴
    if (ans[start])
        return ;
    // 현재 노드와 끝 점이 같다면 Cycle임
    if (start == end)
    {
        // vector안에 들어있는 값들을 다 true 처리
        for (int i = 0 ; i < v.size() ; ++i)
            cycle[v[i]] = true;
        return ;
    }
    
    // 다음 값
    int next = graph[start];
    
    if (!visited[next])
    {
        // 방문한 곳이 아니라면 방문 처리 및 백터에 넣기
        visited[next] = true;
        v.push_back(next);
        depth_first_search(next, end, v);
        visited[next] = false;
        v.pop_back();
    }
}

int main()
{
    // FASTIO
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    for (int Case = 0 ; Case < t ; ++Case)
    {
        memset(visited, 0, sizeof(visited));
        memset(ans, 0, sizeof(ans));
        
        cin >> n;
        int num;
        
        // i + 1번째가 가리키는 값을 담는 배열
        // 1 2 3 4 5 6 7    index
        // 3 1 3 7 3 4 6    가리키는 값
        for (int i = 0 ; i < n ; ++i)
            cin >> graph[i + 1];

        for (int i = 0 ; i < n ; ++i)
        {
            if (cycle[i + 1]) // 사이클이라면 볼 필요가 없으므로 continue
                continue;
            vector<int> state;                 // 사이클의 값들을 담을 vector
            state.push_back(graph[i + 1]);     // i + 1이 가리키는 값을 먼저 넣음
            depth_first_search(graph[i + 1], i + 1, state);    // (i + 1이 가리키는 값, 끝나야 하는 값, 사이클 값들의 vecotr)
            state.pop_back();
            visited[i + 1] = true;            // 방문한 곳은 방문할 이유가 없음
        }
        
        // 개수 세기
        int count  = 0;
        for (int i = 1 ; i < n + 1 ; ++i)
            // true가 아닌 값들이 답임
            if (!cycle[i])
                count++;
        cout << count << '\n';
    }
}

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

문제

문제

출처

ICPC

c++ 9466 시간 초과

hena_42 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말