💎강의내용
58강은 DFS의 관한 내용이었다.
강의 내용중에서 중요하다고 생각되는 부분은
1) 그래프를 리스트에서 나타내는 방법
2) DFS를 표현하는 재귀함수
3) DFS의 재귀함수에서의 task 작업 위치에 따라 달라지는 순회방식
💎소스
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
void D(int v){
if(v > 7) return;
else{
D(v*2);
D(v*2+1);
}
}
int main(){
D(1);
return 0;
}-
소스코드에 대한 설명을 하자면 D라는 함수를 통해서 DFS를 그리게 된다. 가상의 stack 구조를 생각하며 아규먼트 값이 입력된 D가 쌓인다 생각을 하고 그렇게 쌓인 D를 그래프라고 생각하면 된다.
-
이 소스 코드는 결론적으로 아래 사진과 같은 결과를 도출한다.
-
위의 사진을 보면 순번이 있는데 각 순번을 지날 때마다 바로바로 임무를 수행하면 즉 print(v)를 해주면 이는 전위 순회이다.
-
함수에서 D(v*2) 가 끝난 후 임무를 수행 할 시의 순서는
1 2 3 (D[4] task) (D[2] task) 4 (D[5] task) (D[1] task)
5 6 (D[6] task) (D[3] task) 7 (D[7] task)
즉 4 2 5 1 6 3 7 순으로 출력되는 중위 순회가 일어난다. -
다음은 함수에서 D(v*2+1) 가 끝 난 후 임무를 수행 할 시의 순서는
1 2 3 (D[4] task) 4 (D[5] task) (D[2] task)
5 6 (D[6] task) 7 (D[7] task) (D[3] task) (D[1] task)
즉 4 5 2 6 7 3 1 순으로 출력되는 후위 순회가 일어난다. -
여기서 중요하게 볼 부분은 후위 순회이다. 후위 순회 방법을 통해서 병합정렬의 merge 부분을 처리 할 수 있다. 먼저 반을 잘라서 한쪽을 그래프로 다 쪼갠 후 밑 바닥부터 병합하면서 올라오기 때문
이번 강의를 통해서 기억해야 할 부분이라 생각하는 것
재귀함수의 경우 재귀가 일어나는 곳을 기준으로 위 아래 사이에 대해서 임무가 일어나는 시간이 달라진다. 먼저 맨위에 놓게되면 전위순회, 중간에 놓게되면 중위순회, 맨 밑에 놓게되면 후위순회가 일어난다.
