글 읽기 - [c언어] 시간초과네요.....dfs도 해봤고 bfs도 해봤는데......

blutics 5년 전 0

링크 리스트를 사용해서 각 노드들에 간선을 리스트에 저장하고

그 리스트는 array에 저장하였습니다.

그리고 각각 들어오는 간선정보는 nodes에 저장하여 리스트에 연결시켯습니다.

node는 10만개까지 들어오므로 10개에 그리고 나중에

답구할때 링크리스트를 또 쓸꺼라서 넉넉하게 12만개를 전역에 할당받았습니다.

처음에는 printf가 문젠가 해서 sprintf로 문자열을 하나로 합쳐서 printf를 한번만 호출하게 했는데도 시간초과네요.

sprintf도 타임을 많이 잡아먹는건가요?

음.....

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

typedef struct Lnode{
  int index;
  struct Lnode* next;
}Lnode;

typedef struct List{
  int count;
  Lnode* head;
  Lnode* tail;
}List;

char       visit[10002];
List       array[10001];
int  results[10001]={0};
Lnode     nodes[120001];
int                   n;
int               lines;
int          node_count;

List* createList(){
  List* tmp = (List*)malloc(sizeof(List));
  tmp->count = 0;
  tmp->head = NULL;
  tmp->tail = NULL;
  return tmp;
}

Lnode* createLnode(int n){
  Lnode* tmp = &nodes[node_count++];
  tmp->index = n;
  tmp->next = NULL;
  return tmp;
}

void insert(List* list, int number){
  if(list->count==0){
    list->head=createLnode(number);
    list->tail=list->head;
  }else{
    list->tail->next=createLnode(number);
    list->tail=list->tail->next;
  }
  list->count++;
}

void setData(){
  int  a=0;
  int  b=0;
  scanf("%d %d", &n, &lines);
  for(int i=0;i<n+1;i++){
    array[i].count=0;
    array[i].head=NULL;
    array[i].tail=NULL;
  }
  for(int i=0;i<lines;i++){
    scanf("%d %d", &a, &b);
    insert(&array[b], a);
  }
}

int dfs(int n){
  int computers=0;
  Lnode* tmp=array[n].head;
  visit[n]=1;
  while(tmp!=NULL){
    if(visit[tmp->index]==0){
      visit[tmp->index]=1;
      computers+=dfs(tmp->index)+1;
    }
    tmp=tmp->next;
  }
  return computers;
}
int dfs_start(int n){
  if(array[n].count==0) return 1;
  for(int i=0;i<10002;i++) visit[i]=0;
  return dfs(n)+1;
}
int main(){
  int MAX=0;
  setData();
  for(int i=0;i<n+1;i++){
    results[i]=dfs_start(i);
    if(results[i]>MAX){
      MAX=results[i];
    }
  }
  List* result=createList();
  for(int i=0;i<n+1;i++){
    if(results[i]==MAX){
      insert(result, i);
    }
  }
  Lnode* tmp=result->head;
  char str[50000];
  char buffer[10];
  while(tmp!=NULL){
    if(tmp->next!=NULL){
      sprintf(buffer, "%d ", tmp->index);
    }else{
      sprintf(buffer, "%d\n", tmp->index);
    }
    strcat(str, buffer);
    tmp=tmp->next;
  }
  printf("%s",str);
  return 0;
}

djm03178 5년 전 1

다른 건 좀 더 봐야겠지만, 문자열을 지금과 같이 하나로 이어붙여나가는 건 길이의 제곱에 비례하는 시간이 걸려 더 비효율적입니다. strcat이 문제인데, 이 함수는 첫 번째 문자열의 끝이 어디인지 찾기 위해 문자열의 처음부터 널 문자가 나타나는 지점까지 하나씩 탐색해야 합니다.

blutics 5년 전 0

문자열 합치는 부분을 싹지워 버리고 간소화 시켰습니다.

간소화시킬 수 있는 부분이었는데 너무 복잡하게 생각했었네요.

그래도 시간초과네요 흠....

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

typedef struct Lnode{
  int index;
  struct Lnode* next;
}Lnode;

typedef struct List{
  int count;
  Lnode* head;
  Lnode* tail;
}List;

char       visit[10002];
List       array[10001];
int  results[10001]={0};
Lnode     nodes[120001];
int                   n;
int               lines;
int          node_count;

Lnode* createLnode(int n){
  Lnode* tmp = &nodes[node_count++];
  tmp->index = n;
  tmp->next = NULL;
  return tmp;
}

void insert(List* list, int number){
  if(list->count==0){
    list->head=createLnode(number);
    list->tail=list->head;
  }else{
    list->tail->next=createLnode(number);
    list->tail=list->tail->next;
  }
  list->count++;
}

void setData(){
  int  a=0;
  int  b=0;
  scanf_s("%d %d", &n, &lines);
  for(int i=0;i<n+1;i++){
    array[i].count=0;
    array[i].head=NULL;
    array[i].tail=NULL;
  }
  for(int i=0;i<lines;i++){
    scanf_s("%d %d", &a, &b);
    insert(&array[b], a);
  }
}

int dfs(int n){
  int computers=0;
  Lnode* tmp=array[n].head;
  visit[n]=1;
  while(tmp!=NULL){
    if(visit[tmp->index]==0){
      visit[tmp->index]=1;
      computers+=dfs(tmp->index)+1;
    }
    tmp=tmp->next;
  }
  return computers;
}
int dfs_start(int n){
  if(array[n].count==0) return 1;
  for(int i=0;i<10002;i++) visit[i]=0;
  return dfs(n)+1;
}
int main(){
  int MAX=0;
  setData();
  for(int i=0;i<n+1;i++){
    results[i]=dfs_start(i);
    if(results[i]>MAX){
      MAX=results[i];
    }
  }
  for(int i=0;i<n+1;i++){
    if(results[i]==MAX){
      printf("%d ", i);
    }
  }
  return 0;
}

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

문제

문제

출처

ICPC

[c언어] 시간초과네요.....dfs도 해봤고 bfs도 해봤는데......

blutics 5년 전 0

djm03178 5년 전 1

blutics 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말