글 읽기 - (C언어) 시간복잡도 관련 질문드립니다. (뉴비 좀 살려주세요ㅠㅠ)

ian981130s 3년 전 0

BFS를 이용해 문제를 풀려했습니다.

그래프는 인접리스트를 이용해 표현하였고, BFS를 위한 큐는 링크드리스트를 이용해 구현했습니다.

예제들의 경우 맞게 나오는데, 계속해서 12%까지 채점 후 시간초과가 나옵니다.

어느부분에서 시간복잡도를 줄일 수 있는지 고수님들의 조언 부탁드립니다.

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

int V, E;
int BFSVisit[20001] = {0,}; //번갈아가며 1, -1을 노드에 마킹해줌
int IsBipartite; //이분그래프면 1, 아니면 0

/*****************Queue를 Linked-List로 구현 부분*******************************/ 
typedef struct _Node{
	struct _Node *next;
	int NumOfNode;
}Node;


typedef struct _Queue{
	struct _Node *first;
	struct _Node *last;
	int size;
}Queue;


void QueueInit(Queue *pQueue)
{
	pQueue->first = NULL;
	pQueue->last = NULL;
	pQueue->size = 0;
}


void Enqueue(Queue *pQueue, int data)
{
	Node *newNode = (Node*)malloc(sizeof(Node));
	
	newNode->next = NULL;
	newNode->NumOfNode = data;
	
	if(pQueue->size==0)
	{
		pQueue->first = newNode;
		pQueue->last = newNode;
		(pQueue->size)++;
	}
	
	else
	{
		pQueue->last->next = newNode;
		pQueue->last = newNode;
		(pQueue->size)++;	
	}
}


void Dequeue(Queue *pQueue)
{
	if(pQueue->size==0)
		return;
		
	pQueue->first = pQueue->first->next;
	(pQueue->size)--;
}
/****************************************************************************/


/*********************각각의 노드에 대해 인접리스트 구현****************/ 
struct _Node *Bucket[20001];

void AddBucket(int Index, int data)
{
	Node *curr = Bucket[Index];
	
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->NumOfNode = data;
	
	while(curr->next != NULL)
		curr = curr->next;
		
	curr->next = newNode;
}
/***************************************************************/

void BFS(Queue *pQueue, int StartNode)
{
	int tmp, dequeue;
	int idx;
	Node *curr;
	
	Enqueue(pQueue, StartNode);//처음노드를 큐에 넣어줌
	BFSVisit[StartNode] = 1;//처음노드는 1로 마킹
	
	while(pQueue->size > 0) //모든노드 탐색
	{
		dequeue = pQueue->first->NumOfNode;//디큐를 해줌
		Dequeue(pQueue);
		
		curr = Bucket[dequeue]->next;
		
		while(1) //dequeue와 모든 인접한 노드 탐색
		{
			if(curr==NULL)
				break;
				
			tmp = curr->NumOfNode;
			
			if(BFSVisit[tmp]==0)//만약 전에 방문하지 않은 노드라면
			{
				Enqueue(pQueue, tmp);//큐에 넣어준 뒤
				BFSVisit[tmp] = BFSVisit[dequeue]*(-1);//그전 노드에서 -1곱한값을 마킹해줌
			}
			
			else //만약 방문한 노드인데
			{
				if(BFSVisit[dequeue]==BFSVisit[tmp])//마킹한 값이 인접한 노드와 같다면
				{
					IsBipartite = 0;//이분그래프가 아니면
					return;//그 뒤를 탐색할 필요 없이 바로 return해준다.
				}
			}
			
			curr = curr->next;
		}
	}
}


int main()
{
	int TestCase;
	int Node1, Node2;
	int idx, jdx, i;
	
	scanf("%d", &TestCase);
	
	Queue *pQueue = (Queue*)malloc(sizeof(Queue));
	
    for(idx=0 ; idx<=20000 ; idx++)
		Bucket[idx] = (Node*)malloc(sizeof(Node));
		
	for(i=0 ; i<TestCase ; i++)
	{
		scanf("%d %d", &V, &E);
		
		for(idx=1 ; idx<=V ; idx++) //버킷을 초기화 해준 뒤
			Bucket[idx]->next = NULL;
			
		for(idx=0 ; idx<E ; idx++) //각각의 버켓에 인접한 노드를 넣어준다.
		{
			scanf("%d %d", &Node1, &Node2);
							
			AddBucket(Node1, Node2);
			AddBucket(Node2, Node1);
		}
		
	
		for(idx=1 ; idx<=V ; idx++)//모든 노드에 대해 탐색
		{
			QueueInit(pQueue);
			IsBipartite = 1;
			
			for(jdx=0 ; jdx<=20000 ; jdx++) 
				BFSVisit[jdx] = 0;
		
			BFS(pQueue, idx);
			
			if(IsBipartite==0)//만약 이분그래프가 아니면 출력	
				break;
		}
		
		if(IsBipartite==0)
			printf("No\n");
		else
			printf("YES\n");
	}
}

dtc03012 3년 전 0

왜 모든 정점에서 다 돌리는거에요? 한 정점에서만 돌아도 되지 않나요? 그렇게 짜면 V*V*E 아닌가?

dtc03012 3년 전 0

아니 V*(V+E) 요

ian981130s 3년 전 0

그래프가 연결그래프라는 보장이 없어서 모든 노드에 대해 탐색했습니다!!

혹시 하나의 노드에 대해서만 돌려도 이상이 없을까요??

dtc03012 3년 전 0

그럼 방문하지 않은 정점에서만 돌려주면 될거에요

ian981130s 3년 전 0

dtc03012님 말대로 IsVisit[] 를 추가해서 방문했는지 확인해서 방문하지 않는 노드만 탐색하는걸로 했는데도 시간초과가 나네요...

혹시 다른 방법이 있을까요...??

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

int V, E;
int BFSVisit[20001] = {0,}; //번갈아가며 1, -1을 노드에 마킹해줌
int IsBipartite; //이분그래프면 1, 아니면 0
int IsVisit[20001];
/*****************Queue를 Linked-List로 구현 부분*******************************/ 
typedef struct _Node{
	struct _Node *next;
	int NumOfNode;
}Node;


typedef struct _Queue{
	struct _Node *first;
	struct _Node *last;
	int size;
}Queue;


void QueueInit(Queue *pQueue)
{
	pQueue->first = NULL;
	pQueue->last = NULL;
	pQueue->size = 0;
}


void Enqueue(Queue *pQueue, int data)
{
	Node *newNode = (Node*)malloc(sizeof(Node));
	
	newNode->next = NULL;
	newNode->NumOfNode = data;
	
	if(pQueue->size==0)
	{
		pQueue->first = newNode;
		pQueue->last = newNode;
		(pQueue->size)++;
	}
	
	else
	{
		pQueue->last->next = newNode;
		pQueue->last = newNode;
		(pQueue->size)++;	
	}
}


void Dequeue(Queue *pQueue)
{
	if(pQueue->size==0)
		return;
		
	pQueue->first = pQueue->first->next;
	(pQueue->size)--;
}
/****************************************************************************/


/*********************각각의 노드에 대해 인접리스트 구현****************/ 
struct _Node *Bucket[20001];

void AddBucket(int Index, int data)
{
	Node *curr = Bucket[Index];
	
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->NumOfNode = data;
	
	while(curr->next != NULL)
		curr = curr->next;
		
	curr->next = newNode;
}
/***************************************************************/

void BFS(Queue *pQueue, int StartNode)
{
	int tmp, dequeue;
	int idx;
	Node *curr;
	
	Enqueue(pQueue, StartNode);//처음노드를 큐에 넣어줌
	BFSVisit[StartNode] = 1;//처음노드는 1로 마킹
	IsVisit[StartNode] = 1;
	while(pQueue->size > 0) //모든노드 탐색
	{
		dequeue = pQueue->first->NumOfNode;//디큐를 해줌
		Dequeue(pQueue);
		
		curr = Bucket[dequeue]->next;
		
		while(1) //dequeue와 모든 인접한 노드 탐색
		{
			if(curr==NULL)
				break;
				
			tmp = curr->NumOfNode;
			
			if(BFSVisit[tmp]==0)//만약 전에 방문하지 않은 노드라면
			{
				Enqueue(pQueue, tmp);//큐에 넣어준 뒤
				BFSVisit[tmp] = BFSVisit[dequeue]*(-1);//그전 노드에서 -1곱한값을 마킹해줌
				IsVisit[tmp] = 1;
			}
			
			else //만약 방문한 노드인데
			{
				if(BFSVisit[dequeue]==BFSVisit[tmp])//마킹한 값이 인접한 노드와 같다면
				{
					IsBipartite = 0;//이분그래프가 아니면
					return;//그 뒤를 탐색할 필요 없이 바로 return해준다.
				}
			}
			
			curr = curr->next;
		}
	}
}


int main()
{
	int TestCase;
	int Node1, Node2;
	int idx, jdx, i;
	
	scanf("%d", &TestCase);
	
	Queue *pQueue = (Queue*)malloc(sizeof(Queue));
	
    for(idx=0 ; idx<=20000 ; idx++)
		Bucket[idx] = (Node*)malloc(sizeof(Node));
		
	for(i=0 ; i<TestCase ; i++)
	{
		scanf("%d %d", &V, &E);
		
		for(idx=1 ; idx<=V ; idx++)//버킷을 초기화 해준 뒤
		{ 
			Bucket[idx]->next = NULL;
			IsVisit[idx] = 0;
		}
			
		for(idx=0 ; idx<E ; idx++) //각각의 버켓에 인접한 노드를 넣어준다.
		{
			scanf("%d %d", &Node1, &Node2);
							
			AddBucket(Node1, Node2);
			AddBucket(Node2, Node1);
		}
		
	
		for(idx=1 ; idx<=V ; idx++)//모든 노드에 대해 탐색
		{
			QueueInit(pQueue);
			IsBipartite = 1;
			
			for(jdx=0 ; jdx<=20000 ; jdx++) 
				BFSVisit[jdx] = 0;
			
			if(IsVisit[idx] == 0)
				BFS(pQueue, idx);
			
			if(IsBipartite==0)//만약 이분그래프가 아니면 출력	
				break;
		}
		
		if(IsBipartite==0)
			printf("No\n");
		else
			printf("YES\n");
	}
}

dtc03012 3년 전 0

164 ~ 165 번째 줄에 2만을 돌려서 V*20000이 되서 시간초과가 나는 것 같네요 코드가 너무길어서 다 읽지를 못하겠는데 BFSVisit 를 왜 초기화 시켜주는 거에요? 어차피 그 다음에 방문할 노드는 isvisited 에 체크가 안된 노드기 때문에 BFSVisit 는 초기화된 값이여서 저 164~165 줄이 필요가 없을것같은데..

ian981130s 3년 전 0

그러네요..!!

그런데 말씀대로 아래 코드를 돌려보니 예제들은 맞게 나오는데 역시 시간초과가 뜨네요...

혹시 BFS()함수에서 시간복잡도가 너무 많이 나오는게 아닐까요..??

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

int V, E;
int BFSVisit[20001] = {0,}; //번갈아가며 1, -1을 노드에 마킹해줌
int IsBipartite; //이분그래프면 1, 아니면 0
int IsVisit[20001];
/*****************Queue를 Linked-List로 구현 부분*******************************/ 
typedef struct _Node{
	struct _Node *next;
	int NumOfNode;
}Node;


typedef struct _Queue{
	struct _Node *first;
	struct _Node *last;
	int size;
}Queue;


void QueueInit(Queue *pQueue)
{
	pQueue->first = NULL;
	pQueue->last = NULL;
	pQueue->size = 0;
}


void Enqueue(Queue *pQueue, int data)
{
	Node *newNode = (Node*)malloc(sizeof(Node));
	
	newNode->next = NULL;
	newNode->NumOfNode = data;
	
	if(pQueue->size==0)
	{
		pQueue->first = newNode;
		pQueue->last = newNode;
		(pQueue->size)++;
	}
	
	else
	{
		pQueue->last->next = newNode;
		pQueue->last = newNode;
		(pQueue->size)++;	
	}
}


void Dequeue(Queue *pQueue)
{
	if(pQueue->size==0)
		return;
		
	pQueue->first = pQueue->first->next;
	(pQueue->size)--;
}
/****************************************************************************/


/*********************각각의 노드에 대해 인접리스트 구현****************/ 
struct _Node *Bucket[20001];

void AddBucket(int Index, int data)
{
	Node *curr = Bucket[Index];
	
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->NumOfNode = data;
	
	while(curr->next != NULL)
		curr = curr->next;
		
	curr->next = newNode;
}
/***************************************************************/

void BFS(Queue *pQueue, int StartNode)
{
	int tmp, dequeue;
	int idx;
	Node *curr;
	
	Enqueue(pQueue, StartNode);//처음노드를 큐에 넣어줌
	BFSVisit[StartNode] = 1;//처음노드는 1로 마킹
	IsVisit[StartNode] = 1;
	while(pQueue->size > 0) //모든노드 탐색
	{
		dequeue = pQueue->first->NumOfNode;//디큐를 해줌
		Dequeue(pQueue);
		
		curr = Bucket[dequeue]->next;
		
		while(1) //dequeue와 모든 인접한 노드 탐색
		{
			if(curr==NULL)
				break;
				
			tmp = curr->NumOfNode;
			
			if(BFSVisit[tmp]==0)//만약 전에 방문하지 않은 노드라면
			{
				Enqueue(pQueue, tmp);//큐에 넣어준 뒤
				BFSVisit[tmp] = BFSVisit[dequeue]*(-1);//그전 노드에서 -1곱한값을 마킹해줌
				IsVisit[tmp] = 1;
			}
			
			else //만약 방문한 노드인데
			{
				if(BFSVisit[dequeue]==BFSVisit[tmp])//마킹한 값이 인접한 노드와 같다면
				{
					IsBipartite = 0;//이분그래프가 아니면
					return;//그 뒤를 탐색할 필요 없이 바로 return해준다.
				}
			}
			
			curr = curr->next;
		}
	}
}


int main()
{
	int TestCase;
	int Node1, Node2;
	int idx, jdx, i;
	
	scanf("%d", &TestCase);
	
	Queue *pQueue = (Queue*)malloc(sizeof(Queue));
	
    for(idx=0 ; idx<=20000 ; idx++)
		Bucket[idx] = (Node*)malloc(sizeof(Node));
		
	for(i=0 ; i<TestCase ; i++)//각각의 테스트케이스에 대해 실행
	{
		scanf("%d %d", &V, &E);
		
		for(idx=1 ; idx<=V ; idx++)//버킷을 초기화 해준 뒤
		{ 
			Bucket[idx]->next = NULL;
			IsVisit[idx] = 0;
		}
			
		for(idx=0 ; idx<E ; idx++) //각각의 버켓에 인접한 노드를 넣어준다.
		{
			scanf("%d %d", &Node1, &Node2);
							
			AddBucket(Node1, Node2);
			AddBucket(Node2, Node1);
		}
		
	
		for(idx=1 ; idx<=V ; idx++)//모든 노드에 대해 탐색
		{
			if(IsVisit[idx]==1)//방문했던 노드면 탐색하지 않음
				continue;
			
			QueueInit(pQueue);
			IsBipartite = 1;
			
			BFS(pQueue, idx);
								
			if(IsBipartite==0)//만약 이분그래프가 아니라면	
				break;//탐색종료
		}
		
		if(IsBipartite==0)
			printf("No\n");
		else
			printf("YES\n");
	}
}

dtc03012 3년 전 0

75 ~ 76 줄에서 넣을때마다 모든 인접리스트 다 돌기때문에 E*E 가 될 것 같네요 tail 배열 하나 만들어서 tail 끝에다가 추가하는 식으로 하면 추가할 때 O(1) 일거에요

ian981130s 3년 전 0

아 이제 시간초과는 뜨지 않네요..!!(대신 틀렸다고는 뜨지만..ㅠㅠ)

이부분은 제가 더 고민해보겠습니다.

답변 정말 감사드립니다!!

ian981130s 3년 전 0

허허 마지막 출력에 No->NO로 바꾸니 맞네요....

다시한번 답변 남겨주셔서 감사합니다.

dtc03012 3년 전 0

열공하세요 ㅎㅎ

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

문제

문제

출처

ICPC

(C언어) 시간복잡도 관련 질문드립니다. (뉴비 좀 살려주세요ㅠㅠ)

ian981130s 3년 전 0

dtc03012 3년 전 0

dtc03012 3년 전 0

ian981130s 3년 전 0

dtc03012 3년 전 0

ian981130s 3년 전 0

dtc03012 3년 전 0

ian981130s 3년 전 0

dtc03012 3년 전 0

ian981130s 3년 전 0

ian981130s 3년 전 0

dtc03012 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말