[C++] Tree+DFS

DFS(Depth Fisrt Search)

• 그래프의 연결 노드간 관계를 파악해 출발 노드에서 도착 노드까지 가장 빠르게 가는 방법.
• 모든 점을 둘러본다.(완전탐색)
• 출발점에서 갈 수 있는 끝 점까지 쳌
• 다양한 경로를 들려보는 탐색(DFS만의 특징)

DFS 특징
-> 1) 단순히 모든 점을 1번씩 들려보는 탐색(=BFS)
2) 다양한 경로(다양한 방식) 들려보는 탐색(*중요)(**DFS만의 특징)

• 재귀는 그래프라고 생각할 수 있다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;
int arr[100][100] = { 0, };
int cntNode;

void dfs(int now) // now는 출발점.
{
	// 인접행렬 arr[now][???] == 1 이면 방문 가능!

	// 종료 (필수 X)
	/* if (끝날 조건) {

	} */

	cout << now << " ";
	for (int next = 1; next <= cntNode; next++) {
		if (arr[now][next] == 0)
			continue;
		dfs(next);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 인접 행렬 저장
	cin >> cntNode;
	for (int i = 0; i < cntNode - 1; i++) {
		int parent, child;
		cin >> parent >> child;
		arr[parent][child] = 1;
	}

	// DFS : depth first search - 재귀

	// 1번 노드에서 시작해서 모든 노드를 방문
	dfs(1);


	return 0;
}

🎳다양한 경로 찾기

vector<int> path;

void dfs(int now) {
	// 종료 조건
    // 목적지에 도달하면 시작점부터 목적지까지의 path를 출력한다.
	if (now == end) {
		for (int i = 0; i < path.size(); i++) {
			cout << path[i] << " ";
		}
		cout << "\n";
		return;
	}
	
	for (int next = 1; next <= cntNode; next++) {
		if (arr[now][next] == 0) continue;
		if (check[next] == 1) continue;
        // 방문체크 + path 추가
     	// 방문체크로 중복된 경로 방지
		check[next] = 1;
		path.push_back(next);
		dfs(next);
		check[next] = 0; 
		path.pop_back();
	}
}

---

트리

• 노드간 간선이 1개 존재한다.
• 간선의 개수가 노드(N) - 1개 존재

트리의 중심 노드를 Root라고 한다.(가계도와 비슷한 모양)

트리 문제 유형
1. 트리인걸 알려준다.😀
2. 임의 점 두개를 연결하는 가장 짧은 경로 유일하다.😣

---

가지치기 방법

	// 올바른 가지치기
	for (int i = 1; i <= 100; i++) {
		if (가지치기 조건)
			continue;
		if (가지치기 조건)
			continue;
		if (가지치기 조건)
			continue;
		if (가지치기 조건)
			continue;
		실행 코드;
	}
	// 잘못된 가지치기
	for (int next = 1; next <= cntNode; next++) {
		if (실행 조건)
			if (가지치기 조건)
				if (가지치기 조건)
					if (가지치기 조건)
						if (가지치기 조건)
							실행 코드;
	}

Thank you (●'◡'●)