글 읽기 - 시간초과 나는 이유를 도무지 모르겠습니다 ㅠㅠ

juju22 6년 전 0

21 3 10
1 2 3
3 4 5
5 6 7
7 10 9
11 9 13
12 13 14
14 15 16
16 18 19
17 18 19
20 18 21

output 10

21 3 10
1 2 3
3 4 5
5 6 7
7 10 9
11 9 13
12 13 14
14 15 16
16 18 19
17 18 19
20 8 21

output -1

만든 테스트는 잘 나오는데.. ㅠㅠ 뭐가 문제일까요,,,???

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

using namespace std;

int main(int argc, const char * argv[]) {
    // insert code here...
    int N, K, M;
    
    scanf("%d%d%d", &N, &K, &M);
    
    vector<vector<int>> hyper(M + 1, vector<int>(K + 1));\
    vector<bool> visit(N, false);
    for(int i = 0; i < M; i++){
        for(int j = 0; j < K; j++){
            scanf("%d", &hyper[i][j]);
        }
    }
    
    int cur, cnt = 0;
    queue<pair<int, int>> q;
    q.push({1, 1});
    visit[1] = true;
    while(!q.empty()){
        
        cur = q.front().first;
        cnt = q.front().second;
        
        q.pop();
        
        if(cur == N){
            cout << cnt << endl;
            return 0;
        }
        
        for(int i = 0; i < M; i++)
        {
            for(int j = 0; j < K; j++)
            {
                if(hyper[i][j] == cur)
                {
                    
                    do{
                        if(hyper[i][0] == cur || visit[hyper[i][0]]) continue;
                        visit[hyper[i][0]] = true;
                        q.push({hyper[i][0], cnt + 1});
                        
                    }while(next_permutation(hyper[i].begin(), hyper[i].end()));
                }
                
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

cheetose 6년 전 0

next_permutation의 시간복잡도는 O(n!)이라서 시간초과가 납니다.

cheetose 6년 전 0

정확히는 저 next_permutation의 시간복잡도는 amortized O(1)인데 n!번을 해야 저 반복문이 종료돼요

juju22 6년 전 0

저 while 문을 아래처럼 바꿨는데도 시간 초과가 나네요 ㅠㅠ

이 방식으로는 풀 수 없는 걸까요..???

for(auto node : hyper[i])
{
    if(node == cur || visit[node]) continue;
    visit[node] = true;
    // 이동 가능한 노드 추가
    q.push({node, cnt + 1});
                        
}

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

문제

문제

출처

ICPC

시간초과 나는 이유를 도무지 모르겠습니다 ㅠㅠ

juju22 6년 전 0

cheetose 6년 전 0

cheetose 6년 전 0

juju22 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말