DAG 출력 어떻게 하면 좋을까요.
아메
DAG(루프가 없는 방향이 있는 그래프) 데이터가 있습니다.
이때, 한 항목에 대해서 향하고 있는 모든 데이터를 출력하고 싶습니다.
(예.a-b, a-cb-d, b-ec-e라는 데이터가 있으면a라고 입력했을때a,b,c,d,e(a에서 b,c 출력,b가 포함되어있으므로 b가 향하는 d,e 출력.c가 향하는 e 출력)를 출력하고 싶습니다.)
딱히 할 줄 아는 프로그램 언어가 c 밖에 없으니 c로 짜려고 노력중인데 잘 안되네요.처음에는 함수를 하나 만들어서 입력값을 a로 하고 a가 향하고 있는 녀석 b,c를 다시 함수에 넣어서 하는 식으로 만들려고 했는데,문제가... 뭘 부터 설명해야할지 좀 헷갈리지만.우선 b를 함수에 넣습니다. 그리고 b가 향하고 있는 데이터를 확인합니다. 그리고 적당히 d,e 등도 했다고 치고,a-c에서 넣어주기 위해서 돌아옵니다. 그런데 이때 문제가 b에서 이미 읽어들이고 있는 파일 위치를 바꿔서 a-c 인것을 알 수가 없습니다.
(현재 데이터는id abcid bdeid c... 이런 식으로 짜여져 있습니다. 그러니깐 a가 b를 가리키고 있는 위치가 b를 실행하면 b가 가리키는 위치로 이동해야되므로 a가 b다음에 무엇을 가리키는지 알 수 없게 됩니다.)
설명이 너무 애매하게 되었는데... 이해 못하시는 부분 있으면 댓글 달아주세요.
데이터 모양을 바꿔야 풀 수 있을 것 같으면 그렇게 하셔도 됩니다.
마지막으로 항목이 하나가 아니라 여러개 항목으로 할 예정입니다.
예를 들어 a라는 항목과 b라는 항목을 입력값a aa ba ca da eb db e라는 출력을 할 예정입니다.
-
여울가녘
다음에도 좋은 답변 잘 부탁드립니다. 정말 감사했습니닼ㅋ
-
사이
ㅋㅋㅋ 알고있는거였는데 뻘짓했을때가 괜히 억울하고 막 그랬는데 ㅋㅋ
-
텐시
라고 할까 지금 보니 학부때 다 배운거네욬ㅋㅋ 멍청함류 갑ㅋㅋ
-
핑크펄
아 좋은 답변 감사합니다. 마침 글 올리고 자고 일어나니깐 queue나 stack을 이용하면 가능할 것 같아서 어떻게든 지저분하게 짯습니닼ㅋㅋ. 생각해보니 그래프 중 하나니깐 충분히 일반적인 그래프를 내는 녀석을 써도 괜찮겠군요. 여러가지 방법을 알려주셔서 감사합니다. 좀 찾아봐야겠군요. 다음부터 해매지 않도록.
-
블레이
a 를 시작점으로 방문가능한 모든 정점을 순회및 출력하고싶으신 거 같은데(맞나요...)
DFS, BFS 같은 그래프 순회 알고리즘을 쓰시면 될것 같습니다.
DFS를 쓰시겠다면 재귀로 짜도 OK,
메모리가 걱정된다면 링크드리스트 구현해서 짜시구요.
BFS를 쓰시겠다면 큐를 쓰시면 됩니다.
C++이라면 STL 에 queue 컨테이너가 있으니 그걸 쓰시면 되는데
C라면 큐를 구현하셔야 하구요 :)