글 읽기 - dfs 구현 하는 부분에서 막혀서 질문드립니다.

rudxo007 6년 전 0

방향성 제시 부탁드립니다.

createNode 함수를 만들어서 linked-list 에 저장을 하였습니다.

그리고 dfs 함수를 이용해서 목적지까지 가는 경로의 값을 비교해서 구현 하려고 생각하고 있습니다.

dfs 구현하는데 있어서 조건을 어떻게 줘야하고 어떤식으로 나아가야할지 좀 막막한 상황입니다.

도와주시면 감사하겠습니다.

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

typedef struct node *nodePointer;
typedef struct node {
	int data;
	int vertex;
	nodePointer link;
} node;

nodePointer *list;

nodePointer createNode(int data1, int data2, int value[]);
int dfs_s(int n);

int *array, *dfs_ary ;
int sum = 0;

int main(void)
{
	
	int test_case;
	int N, K;
	int i, j;
	int data;
	int path1, path2, end;

	
	scanf("%d", &test_case);
	
	for (i=0; i<test_case; i++) {
		scanf("%d %d", &N, &K);
		
		array = (int *)malloc(sizeof(int)*(N));
		dfs_ary = (int *)malloc(sizeof(int)*(N));
		list = (nodePointer *)malloc(sizeof(list)*(N+2));
		
		for (j=1; j<=N; j++) {
			list[j] = NULL;
			dfs_ary[j] = -1;
		}
		
		for (j=1; j<=N; j++) {
			scanf("%d", &data);
			array[j] = data;
		}
		
		for (j=1; j<=K; j++) {
			scanf("%d %d", &path1, &path2);
		//	list[path1]->link = list[path2];
			createNode(path1, path2, array);
		}
		
		scanf("%d", &end);
		
	
			
		
		
	/*	for (j=1; j<=N; j++) {
			printf("%d : ", j);
			for (; list[j]; list[j]=list[j]->link) {
				printf("%d%d ", list[j]->vertex, list[j]->data);	
			}
			printf("\n");
			
		} */
		
		for (j=1; j<=K; j++) {
			dfs_s(j);
		}
			
		
	} 
	
	
	
	return 0;
}

nodePointer createNode(int data1, int data2, int value[])
{
	nodePointer temp, prev, store;
	
	temp = list[data1];
	
	store = (nodePointer)malloc(sizeof(store));
	store->data = value[data2];
	store->vertex = data2;
	store->link = NULL;
	
	if (!temp) {
		list[data1] = store;
	}
	
	else {
		for (; temp; temp=temp->link) {
			prev = temp;
		}
		prev->link = store;
		
	}
	
	
	
}

int dfs_s(int n)
{
	nodePointer temp = list[n];
	
	//sum += temp->data;	
	printf("%d ", n);	

	if (dfs_ary[n] == 0 || !temp) {
		sum += array[n];
		return 0;
	}
	else {
		dfs_ary[n] = 0;
		sum += temp->data;
		dfs_s(temp->vertex);	
	}
	
	
	
	
	return 0;
}

sgchoi5 6년 전 1

저는 알고리즘 문제 해결전략에 있는 위상 정렬하는 문제 참고해서 우선 위상 정렬 결과를 만들어 냈고요..

28장 고대어 사전 DICTIONARY
- https://algospot.com/judge/problem/read/DICTIONARY
- 풀이: https://github.com/sgchoi5/algorithm/blob/master/28_DICTIONARY.cpp

vector 결과를 reverse() 할 필요없이 처음부터 W 를 찾아서 W를 찾으면 그 때부터 DFS + Memoization 으로 vector 의 끝까지 가면서

최대 비용을 찾았습니다.

vector 에서 W 다음 위치부터, 이 원소를 향하는 모든 원소를 dfs 로 들어가는 것을 반복하면서 뒤로 돌아면서 건설비를 더 합니다 ( dfs / memo 의 전형적인 형태로 )

cost[i] 가 i 번째 지점의 건설비라고 하면 dp[i] 는 i 번째까지의 건설비 중 최대값으로 했습니다.

plzrun 님의 또 다른 설명과 TC 19개는 => https://www.acmicpc.net/board/...

rudxo007 6년 전 1

sgchoi5 님 감사합니다.

이제야 코드를 짤 수 있을거 같습니다. 후

정말 도움 감사드려요 늦었지만 ㅜ

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

문제

문제

출처

ICPC

dfs 구현 하는 부분에서 막혀서 질문드립니다.

rudxo007 6년 전 0

sgchoi5 6년 전 1

rudxo007 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말