글 읽기 - 시간초과 어떻게 해결해야 할까요ㅕ??

gigohe2 2년 전 0

처음에 2차원배열에 0,1로 친구들 저장해서 dfs탐색하였습니다.

이때도 시간초과가 발생하여서 게시판 검색중 인접리스트를 사용하여 탐색하면 n개의 배열을 일일이 탐색하지 않아도 된다는 것을 알게되었고, 인접리스트로 구현해보았습니다.

깊이 0일때는 무조건 friend에 저장하고 방문처리를 하고 깊이 1로 넘어갑니다.

깊이가 1이상일때, i번째 사람의 인접리스트를 가져와 리스트에 그전 친구의 값이 들어있으면, 더 깊이 들어갑니다.

그리고 tru라는 변수를 두어 깊이가 5가되면 tru=1을 해주어 재귀를 종료하게 하였습니다..

전에 작성했던 2차원배열보다는 시간이 줄어든 것 같은데,, 왜 시간초과가 나는걸까요:?ㅠㅠ

#include <stdio.h>
#include <stdlib.h>

int n,m,a,b;


typedef struct nod
{
    struct nod *link;
    int data;
} NODE; //링크드리스트

typedef struct list
{
    NODE *head;
} LIST; //head노드 담을 배열.


LIST *headlist; //전역변수 선언

void add(LIST *start, int c)
{
    NODE *new=(NODE *)malloc(sizeof(NODE));
    new->link=NULL; //뉴노드가 맨 뒷자리에 들어감
    new->data=c;
    
    NODE *cur=(NODE *)malloc(sizeof(NODE));
    cur->link = start->head;
    
    if(start->head == NULL)
    {
        start->head = new;
    }
    while(cur->link != NULL)
    {
        cur = cur->link;
    }
    
    cur->link = new;
    
}

int friend[7];
int visit[2001]={0,};
int ans=0;
int tru=0;

void dfs( int x )
{
    if( x == 5 )
    {
        ans=1;
        tru=1;
    }
    else
    {
        if(tru == 0)
        {
            for(int i=0; i<n; i++) //0~n-1의 노드가 있음
            {
                if(tru == 0)
                {
                    if(x==0) //처음이라면
                    {
                        friend[x] = i;
                        visit[i]=1;
                        dfs(x+1);
                        visit[i]=0;
                    }
                    else // x>=1이라면
                    {
                        NODE *cur;
                        cur=headlist[i].head;
                        
                        while(cur != NULL)
                        {
                            if( cur->data == friend[x-1] ) //만약 친구리스트에 전에놈이 존재
                            {
                                if( visit[i] == 0 ) //아직 사용하지 않았으면
                                {
                                    friend[x] = i;
                                    visit[i] = 1;
                                    dfs(x+1);
                                    visit[i] = 0;
                                    break;
                                }
                            }
                            cur = cur->link;    
                        }
                    }
                }
            }
        }
    }
}


int main()
{
    scanf("%d %d", &n, &m);
    
    headlist = (LIST *)malloc(n*sizeof(LIST)); //head노드 담긴 배열 선언
    
    for(int i=0; i<n; i++)
    {
        
        headlist[i].head = NULL; //헤드노드 초기화
    }
    
    for(int i=0; i<m; i++)
    {
        scanf("%d %d", &a, &b);
        add(&headlist[a], b);
        add(&headlist[b], a);
        
    }
    
    dfs(0);
    
    printf("%d\n", ans);
    
    return 0;
}

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

문제

문제

출처

ICPC

시간초과 어떻게 해결해야 할까요ㅕ??

gigohe2 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말