글 읽기 - 이 코드의 TLE 이유를 해결해 주실 분을 찾습니다..

newdeal 4년 전 0

전처리 과정인 getNextBits함수가 O(2^N)을 사용하고 bfs함수가 O(N 2^N)임을 의도하고 작성한 코드입니다.

하루종일 몇십번을 정독해도 도저히 시간초과 이유가 안보이는 코드는 처음입니다...

공식 데이터 넣어봐도 답은 일치해 로직의 문제는 아닌 것 같습니다.

무려 N이 더 곱해진 시간복잡도가 O(N*2 2^N)인 대회 공식 솔루션 코드를 제출해도 통과하는데, 대체 어디서 시간을 잡아먹고있을까요?😢

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
int N,M,adj[21];
int findNextBits[1<<21];
pair<int,int> parent[1<<21];

int bfs()
{
    vector<int>visited((1<<N),0);
    queue<int>q;
    q.push((1<<N)-1);
    visited[(1<<N)-1]=1;
    while(!q.empty())
    {
        int nowBits=q.front();
        q.pop();
        if(nowBits==0)return visited[nowBits]-1;
        //shots
        for(int i=0;i<N;i++)
        {
            if(!(nowBits&(1<<i)))continue;
            int shotsBits=nowBits^(1<<i);
            //monkeys move
            int nextBits=findNextBits[shotsBits];
            if(visited[nextBits])continue;
            visited[nextBits]=visited[nowBits]+1;
            parent[nextBits]={nowBits,i};
            q.push(nextBits);
        }
    }
    return -1;
}

//이동해야 할 원숭이의 상태:nowBits, 이동한 원숭이의 상태:nextBits
void getNextBits(int nowBits,int nextBits,int idx)
{
    if(idx==N)
    {
        findNextBits[nowBits]=nextBits;
        return ;
    }
    getNextBits(nowBits,nextBits,idx+1);
    getNextBits(nowBits|(1<<idx),nextBits|adj[idx],idx+1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    while(true)
    {
        cin>>N>>M;
        if(N==0&&M==0)break;
        memset(adj,0,sizeof(adj));

        while(M--)
        {
            int u,v;
            cin>>u>>v;
            if(!(adj[u]&(1<<v)))adj[u]|=(1<<v);
            if(!(adj[v]&(1<<u))) adj[v]|=(1<<u);
        }

        getNextBits(0,0,0);
        int ans=bfs();
        if(ans==-1)cout<<"Impossible\n";
        else
        {
            cout<<ans<<": ";
            vector<int>v;
            //역순으로 출력
            for(int p=0;p!=(1<<N)-1;p=parent[p].first)
                v.push_back(parent[p].second);
            for(int i=ans-1;i>=0;i--)cout<<v[i]<<" ";
            cout<<"\n";
        }
    }
    return 0;
}

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

문제

문제

출처

ICPC

이 코드의 TLE 이유를 해결해 주실 분을 찾습니다..

newdeal 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말