글 읽기 - DFS 동적 할당 도와주세요 ㅠㅠ

buc02219 5년 전 0

파일을 읽어서 DFS를 구현하는 코드를 짜고 있는데요

제게 주어진 조건이 정적배열을 사용하지않고 DFS를 구현해야합니다.

어떻게 해야 동작이 제대로 될까요?ㅠㅠ

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


//구조체 --> v: 넣을 위치, connect : v에 연결할 값
struct node {					
	int v;
	struct node *next;
	struct node *left;
	struct node *right;
	struct node *connect;
};

struct node *stack = 0;
struct node *graph = 0;
struct node *visited = 0;


struct node *find_src(int idx)		//src가 있는 위치를 반환
{
	struct node *temp = graph;
	while (temp != 0)
	{
		if (temp->v == idx)
			return temp;
		temp = temp->next;
	}
	return 0;
}

int FindValue(int k)		//graph SLL에 src(넣을 위치)값이 있는지 찾아보기 
{
	struct node *temp = graph;
	while (temp != 0)
	{
		if (temp->v == k)
			return 1;
		temp = temp->next;
	}
	return 0;
}


void _addEdge(int src, int dst)			
{
	struct node *master = (struct node *)malloc(sizeof(struct node));	//넣을 위치값
	master->v = src;
	master->next = 0;
	master->connect = 0;

	struct node *newone = (struct node *)malloc(sizeof(struct node));	//넣을 위치값에 꼬리표로 붙을 값
	newone->v = dst;
	newone->connect = 0;
	newone->next = 0;
	
	//graph->v = master, graph->connect = newone

	if (FindValue(src) == 1)		//일단, graph SLL에 넣을 위치값이 이미 존재하는지 확인
	{
		struct node *find = find_src(src);
		while (find->connect != 0)				//이미 존재한다면 그 값의 connect에 붙여준다 
			find = find->connect->next;
		find->connect->next = newone;
		return;
	}

	if ( graph == 0)		//graph SLL에 아무것도 없다면 그냥 붙이고 나오기 
	{
		graph = master;
		graph->connect = newone;
		return;
	}
	else				//graph SLL에 이미 어떤 값이 존재한다면 마지막을 찾아가서 붙이고 나오기
	{
		struct node *temp = graph;
		while (temp->next != 0)
			temp = temp->next;
		temp->next = master;
		temp->next->connect = newone;
		return;
	}


}


void addEdge(int src, int dst, int weight)
{
	_addEdge(src, dst);
	_addEdge(dst, src);

	struct node *temp = graph;
	while (temp != 0)
	{
		printf("%d-%d", temp->v, temp->connect);
		temp = temp->next;
	}
}

void push(int k)
{
	struct node *newone = (struct node *)malloc(sizeof(struct node));
	newone->v = k;
	newone->next = 0;
	newone->connect = 0;

	newone->next = stack;
	stack = newone;
	return;
}

int pop(void)
{
	if (stack == 0)
		return -999;
	struct node *temp = stack;
	int k = stack->v;
	stack = stack->next;
	free(temp);
	return k;
}


int checkVisited(int k)
{
	struct node *temp = visited;
	while (temp != 0)
	{
		if (temp->v == k)
			return 1;
		if (temp->v > k)
			temp = temp->left;
		else
			temp = temp->right;
	}
	return 0;
}

void addToVisited(int k)
{
	struct node *newone = (struct node *)malloc(sizeof(struct node));
	newone->v = k;
	newone->left = newone->right = 0;

	if (visited == 0)
	{
		visited = newone;
		return;
	}
	struct node *temp = visited;
	while (1)
	{
		if (temp->v > k)
		{
			if (temp->v == 0)
			{
				temp->left = newone;
				return;
			}
			temp = temp->left;
		}
		else
		{
			if (temp->v == 0)
			{
				temp->right = newone;
				return;
			}
			temp = temp->right;
		}
	}


}

struct node *FindFromGraph(int k)
{
	struct node *temp = graph;
	while (temp != 0)
	{
		if (temp->v == k)
			return temp;
		temp = temp->next;
	}
	return 0;
}

void performDFS(int k)
{
	push(k);

	while (1)
	{
		int x = pop();
		if (x == -999)
			return;
		if (checkVisited(x) == 1)
			continue;

		printf("%d ---> ", x);
		addToVisited(x);

		struct node *temp = FindFromGraph(x);
		while (temp != 0)
		{
			if (checkVisited(temp->v) == 0)
			{
				push(temp->v);
			}
			temp = temp->next;
		}

	}
}


int main()
{
	FILE *f = 0;

	f = fopen("data.txt", "rt");

	int v1, v2, v3;

	while (!feof(f))
	{
		fscanf(f, "%d %d %d", &v1, &v2, &v3);

		if (v1 == -1 && v2 == -1 && v3 == -1)
			break;

		addEdge(v1, v2, v3);

	}

	fclose(f);

	performDFS(1);

	return 0;
}

buc02219 5년 전 0

제가 다시 풀었습니다 혹시 다른분들께도 도움이 될수있을것같아서 수정된 코드 첨부합니다 :)

정적 배열을 사용하지 않고 입력받는대로 처리하는 DFS코드에요

#include <stdio.h>
#include <stdlib.h>
struct edge {
	int src;
	int dst;
	struct edge *next;
};
struct vertex {
	int val;
	struct vertex *next;
	struct vertex *left;
	struct vertex *right;
	struct edge *connect;
};
struct edge *edge_head = 0;
struct vertex *vertex_head = 0;
struct vertex *visited = 0;
struct vertex *stack = 0;
int checkVertex(int k)
{
	struct vertex *temp = vertex_head;
	while (temp != 0)
	{
		if (temp->val == k)
			return 1;
		temp = temp->next;
	}
	return 0;
}
void addVertex(int k)
{
	if (checkVertex(k) == 1)
		return;
	struct vertex *newone = (struct vertex *)malloc(sizeof(struct vertex));
	newone->val = k;
	newone->next = 0;
	newone->connect = 0;
	if (vertex_head == 0)
	{
		vertex_head = newone;
		return;
	}
	else
	{
		struct vertex *temp = vertex_head;
		while (temp->next != 0)
			temp = temp->next;
		temp->next = newone;
		return;
	}
}
void _addEdge(int src, int dst)
{
	addVertex(src);
	addVertex(dst);
	struct edge *newone = (struct edge *)malloc(sizeof(struct edge));
	newone->src = src;
	newone->dst = dst;
	newone->next = 0;
	if (edge_head == 0)
	{
		edge_head = newone;
		return;
	}
	else
	{
		struct edge *temp = edge_head;
		while (temp->next != 0)
			temp = temp->next;
		temp->next = newone;
		return;
	}
}
void addEdge(int src, int dst)	//양방향
{
	_addEdge(src, dst);
	_addEdge(dst, src);
}
struct vertex *findVertex(int k)
{
	struct vertex *temp = vertex_head;
	while (temp != 0)
	{
		if (temp->val == k)
			return temp;
		temp = temp->next;
	}
}
void addEdgeInfo(struct vertex *v1, struct vertex *v2)
{
	struct edge *newone = (struct edge *)malloc(sizeof(struct edge));
	newone->dst = v2->val;
	newone->next = 0;
	
	struct edge *temp = v1->connect;
	if (temp == 0)
	{
		v1->connect = newone;
		return;
	}
	else
	{
		while (temp->next != 0)
			temp = temp->next;
		temp->next = newone;
		return;
	}
}
void processEdges()        //몇개가 들어올지 모르니까 들어오는 정보를 저장
{
	struct edge *temp = edge_head;
	while (temp != 0)
	{
		struct vertex *v1 = findVertex(temp->src);
		struct vertex *v2 = findVertex(temp->dst);
		addEdgeInfo(v1, v2);
		addEdgeInfo(v2, v1);
		temp = temp->next;
	}
	
}
void push(int k)
{
	struct vertex *newone = (struct vertex *)malloc(sizeof(struct vertex));
	newone->val = k;
	newone->next = 0;
	newone->connect = 0;
	newone->next = stack;
	stack = newone;
	return;
}
int pop()
{
	if (stack == 0)
		return -999;
	struct vertex *temp = stack;
	int val = stack->val;
	stack = stack->next;
	free(temp);
	return val;
}
int checkVisited(int k)
{
	struct vertex *temp = visited;
	while (temp != 0)
	{
		if (temp->val == k)
			return 1;
		if (temp->val > k)
			temp = temp->left;
		else
			temp = temp->right;
	}
	return 0;
}
void addToVisited(int k)		//방문한 노드를 BST에 추가
{
	struct vertex *newone = (struct vertex *)malloc(sizeof(struct vertex));
	newone->val = k;
	newone->left = newone->right = 0;
	if (visited == 0)
	{
		visited = newone;
		return;
	}
	struct vertex *temp = visited;
	while (1)
	{
		if (temp->val > k)
		{
			if (temp->left == 0)
			{
				temp->left = newone;
				return;
			}
			temp = temp->left;
		}
		else
		{
			if (temp->right == 0)
			{
				temp->right = newone;
				return;
			}
			temp = temp->right;
		}
	}
}
void performDFS(int k)
{
	push(k);
	while (1)
	{
		int x = pop();
		if (x == -999)
		{
			return;
		}
			
		if (checkVisited(x) == 1)
			continue;
		printf("%d --> ", x);
		addToVisited(x);
		struct vertex *temp = findVertex(x);
		struct edge *some = temp->connect;
		while (some != 0)
		{
			if (checkVisited(some->dst) == 0)
				push(some->dst);
			some = some->next;
		}
	}
}
int main()
{
	FILE *f = 0;
	f = fopen("data1.txt", "rt");
	int v1, v2, v3;
	while (!feof(f))
	{
		fscanf(f, "%d %d", &v1, &v2);
		if (v1 == -1 && v2 == -1)		//읽어온 데이터가 -1이면 그만 읽고 빠져나옴
			break;
		addEdge(v1, v2);
	}
	fclose(f);
	processEdges();
	performDFS(2);    //2부터 시작하여 방문할수있는 vertex들을 출력
	
	return 0;
}

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

문제

문제

출처

ICPC

DFS 동적 할당 도와주세요 ㅠㅠ

buc02219 5년 전 0

buc02219 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말