출발지에서 목적지로 향하는 모든 경우 출력

이번에는 출발지에서 목적지로 향할 수 있는 모든 경우를 출력하는 프로그램을 만들어보았습니다. 지금까지 거의 Java만 썼지만 C++도 재미있네요 ㅋㅋ 심심작은 왠지 C++로 구현하는게 나아요... ㅋㅋㅋ

​

특별한 점을 하나 말씀드리자면, 이번에는 알고리즘 기초를 응용해보았습니다. 여기서 사용된 알고리즘은 'DFS 알고리즘' 인데요. DFS(Depth First Search)는 '깊이 우선 탐색' 을 뜻합니다. 간단하게 '갈 수 있을 때 까지 계속 파고든다!' 라고 생각하시면 되요 ㅋㅋㅋ

​

구체적인 알고리즘까지 설명하면 시간이 너무 많이 걸리니까 그냥 생략할께요 ㅠㅠ

출발지와 도착지를 입력받고 모든 루트(Root)를 입력받는 부분입니다. 우선 출발지는 '고등학교 졸업', 도착지는 '취업' 이구요. 결과 화면 만으로는 잘 이해가 안될 것 같아 그림과 함께 설명해드리겠습니다.

위의 그림은 예시에서 사용된 트리(Tree) 입니다. 순서는 왼쪽에서 오른쪽으로만 향하구요.

​

저희가 고등학교를 졸업한 후, 바로 취업할 수도 있고 대학 진학 후에 취업할 수도 있고 대학에 대학원까지 나온 후 취업할 수도 있잖아요 ㅋㅋ 이러한 과정들을 트리로 표현해본 거에요 ㅋㅋㅋ

​

루트를 입력받는다는 것은 한 노드(Node)에서 다른 노드로 향할 수 있는 길을 입력받는다는 뜻입니다. 트리 내의 모든 루트를 정리하면 다음과 같습니다.

​

고등학교 졸업 → 한국 대학교 진학

고등학교 졸업 → 일본 대학교 진학

고등학교 졸업 → 한국 기업 취업

고등학교 졸업 → 일본 기업 취업

한국 대학교 진학 → 한국 기업 취업

한국 대학교 진학 → 일본 기업 취업

한국 대학교 진학 → 한국 대학원 진학

한국 대학교 진학 → 일본 대학원 진학

일본 대학교 진학 → 한국 기업 취업

일본 대학교 진학 → 일본 기업 취업

일본 대학교 진학 → 한국 대학원 진학

일본 대학교 진학 → 일본 대학원 진학

한국 대학원 진학 → 한국 기업 취업

한국 대학원 진학 → 일본 기업 취업

일본 대학원 진학 → 한국 기업 취업

일본 대학원 진학 → 일본 기업 취업

한국 기업 취업 → 취업

일본 기업 취업 → 취업

​

참고로 루트를 입력받는 부분은 위를 입력받은 것입니다. ^^

출발지에서 목적지로 향할 수 있는 모든 경우를 출력하는 부분입니다. 더불어 총 경우의 수 및 길이가 가장 큰 값과 작은 값 까지 입력받게 해보았습니다. 루트의 길이는 전부 다 1로 지정했어요 ㅎㅎㅎ

​

위의 출력 결과는 '고등학교를 졸업 한 후 취업하는 데에는 어떤 방법들이 존재하는가?' 라고 할 수 있습니다. (한국은 물론 일본 대학, 일본 대학원, 일본 기업까지 있다고 가정하구요 ㅋㅋㅋ)

​

※ 가독성을 최대한 높이기 위해 이미지로 제시하였습니다. 아래의 소스코드는 맨 아래쪽에서 다운받으실 수 있습니다.

가장 핵심이 되는 소스코드 입니다. 전에 DFS 알고리즘을 응용했다고 말씀드렸는데요. 반복문 속에서 재귀 함수를 호출함으로써 DFS 응용이 가능했습니다.

​

findDes(src, des, 0, src);

​

초기에는 위와 같이 호출하였구요. src는 출발지, des는 목적지 입니다. roots[][] 는 'A에서 B로 향할 수 있다' 라는 정보를 저장해 놓는 배열이구요.

트리 내의 루트들을 입력받는 부분입니다. ',' 기준으로 분할(split) 하는 부분 구현하느라 조금 애를 썼네요 ㅋㅋㅋ 제가 모두 구현한 건 아니구요. 인터넷에서 찾아보다가 getline() 함수랑 벡터 응용하면 된다는 것을 알게 된겁니다 ㅋㅋ

그리고 trim() 함수 사용한 것도 보이는데, 이것은 양 옆의 공백을 없애주는 역할을 합니다. 이것 역시 인터넷에서 가져온 것이니 설명은 생략.

 

 

<소스 코드>

https://github.com/jhs951101/NumberOfCaseUsingDFS