글 읽기 - bfs 와 dfs 차이

hayman42 6년 전 0

본 문제를 저는 dfs 로 풀었는데 다른 분들것과 시간과 메모리를 비교한 결과 제 코드가 더 안좋다는 것을 확인 할 수 있었는데요,

제 생각엔 dfs 로 하든 bfs 로 하든 알고리즘에선 딱히 다르다고 느껴지지 않았습니다.

집합을 0, 1, 2 로 나누어 0을 방문하지 않은 점들의 집합이라고 하면 현재 점의 집합번호와 다른 0 아닌 번호, 즉 현재 1이면 2, 2면 1로 만들고.

만약 이미 방문 했는데 자신과 똑같다면 실패, 다르면 딱히 더 검사를 안하고 다음으로 넘어가기.

이러한 관점에서는 비슷하다고 생각했는데 제 코드의 시간과 메모리는 다른 똑같은 언어를 쓰신 분들의 것과 비교했을 떄 2~3배 가량 차이가 나네요 ㅠㅠ

혹시 이것이 dfs 가 본 문제에 대해선 bfs 보다 적합하지 않아서인가요? 아니면 제 코드의 문제인가요?

만약 제 코드의 문제라면, 어느 부분에서 문제인지 말씀해 주실 수 있다면 정말 감사하겠습니다.

제가 혼자 하는 것이라 주변에 물어볼 사람이 없어서.. 귀찮으시겠지만 혹시 시간이 나시면 부탁드려요.

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

typedef struct node node;
typedef node *Node;
typedef struct node
{
	int num;
	Node next;
};

Node get_node(int num);
void add_node(Node N, int num);
void del_graph(Node *G, int V);
void get_set_dfs(int num, Node *G, char *set, bool *flag);

int main()
{
	int K, V, E, i, in_1, in_2;
	char *set;        //각 정점이 속한 집합의 번호를 저장. 0, 1, 2의 값을 가짐
	bool flag;        //1일 경우 성공 0일 경우 실패
	Node *graph;        //인접리스트
	scanf("%d", &K);

	while (K--)
	{
		scanf("%d %d", &V, &E);
		set = (char *)calloc((V + 1), sizeof(char)), flag = 1;
		graph = (Node *)malloc((V + 1) * sizeof(Node));
		for (i = 1;i <= V;i++)
			graph[i] = get_node(i);

		for (i = 0;i < E;i++)
		{
			scanf("%d %d", &in_1, &in_2);        //인접리스트
			add_node(graph[in_1], in_2);
			add_node(graph[in_2], in_1);
		}

		for (i = 1;flag && i <= V;i++)
		{
			if (!set[i])
			{
				set[i] = 1;
				get_set_dfs(i, graph, set, &flag);
			}
		}

		if (flag)
			printf("YES\n");
		else
			printf("NO\n");
		del_graph(graph, V);
	}

	return 0;
}

Node get_node(int num)
{
	Node N = (Node)malloc(sizeof(node));
	N->num = num;
	N->next = NULL;
	return N;
}

void add_node(Node N, int num)
{
	Node temp = N;
	while (temp->next)
	{
		temp = temp->next;
		if (temp->num == num)
			return;
	}
	
	temp->next = get_node(num);
}

void del_graph(Node *G, int V)
{
	Node temp;
	int i;

	for (i = 1;i <= V;i++)
	{
		while (G[i]->next)
		{
			temp = G[i]->next;
			G[i]->next = temp->next;
			free(temp);
		}
		free(G[i]);
	}
    
	free(G);
}

void get_set_dfs(int num, Node *G, char *set, bool *flag)
{
	if (!(*flag))        //이미 실패했으므로 더이상의 탐색은 진행되지 않습니다.
		return;

	Node temp = G[num]->next;
	while (temp)
	{
		if (!set[temp->num])        //검사하려는 집합 번호가 0일 경우
		{
			set[temp->num] = set[num] % 2 + 1;        //1일 경우 2, 2일 경우 1로 초기화
			get_set_dfs(temp->num, G, set, flag);        //dfs
		}
		else if (set[temp->num] == set[num])        //같을 경우
		{
			*flag = 0;        //flag의 값이 0이므로 더이상의 탐색은 진행되지 않습니다.
			return;
		}

		temp = temp->next;        //그 외엔 아무 일도 일어나지 않습니다.
	}
}

djm03178 6년 전 0

연결리스트가 너무 무거워서가 아닌가 생각됩니다. 실제로 유용한 정보는 num 1개 (4바이트)인데, next 포인터가 8바이트나 되기 때문에 오버헤드가 상당히 큽니다.

게다가 set은 메모리 해제를 해주지 않는 것 같습니다.

doju 6년 전 0

시간이 오래 걸리는 것은 그래프를 만드는 부분이 아주 비효율적이기 때문입니다. 시간 초과가 나지 않는 것이 신기할 정도네요.
인접 리스트의 끝까지 따라가지 않고 좀 더 빠르게 노드를 추가하는 방법을 생각해 보세요.

hayman42 6년 전 0

djm님 감사드립니다. 그런데 그렇다고 노드 포인터를 안 쓸순 없는데.. 어찌 해야하나요?

Doju님도 감사드립니다. 제가 생각 했을 땐 중복되는 입력에 대해서 예외처리를 하려고 위 방식을 택 한 것이였는데.. 곰곰히 생각해보니 일정한 좋은 성능을 보장한다는 면에선 말씀해주신 방법이 더 좋겠네요.

djm03178 6년 전 0

C로 메모리를 적게 사용해서 푸신 분들을 보니 대체로 간선들을 따로 모아 하나의 배열에 저장해두고, 정렬을 해서 접근하는 방법을 쓰셨습니다. 사실 이쪽이나 저쪽이나 좀 귀찮은 일이기는 합니다. 저도 링크드 리스트로 풀었어서 메모리를 많이 먹었었고요.

반면 C++의 경우 주로 vector로 간선 정보를 저장하게 되는데 vector는 원소가 많아지면 자동으로 크기가 늘어나는 동적 배열이라 메모리 오버헤드도 크지 않을 뿐더러 구현이 아주 간편합니다. 그래서 C++ 코드들은 대체로 메모리 사용량도 적고 코드도 간결합니다.

hayman42 6년 전 0

역시 풀어도 더 배울것만 늘어나네요 ㅋㅋ ㅠㅠ 답변 감사드립니다~

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

문제

문제

출처

ICPC

bfs 와 dfs 차이

hayman42 6년 전 0

djm03178 6년 전 0

doju 6년 전 0

hayman42 6년 전 0

djm03178 6년 전 0

hayman42 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말