백준 15681 트리와 쿼리

이제 bfs는 하겠는데 dfs는 바로바로 써먹으려니 아직 좀 헷갈린다

 

dfs 

재귀호출하거나 스택을 이용해서 사용할 수 있다. 

 

재귀호출 이용시 인접 노드들을 for문으로 방문하면서 그 인접노드에 대해 dfs를 다시 시행해 단말노드까지 도달한다. 

예시

 

스택을 이용할 경우 스택에 인접 노드들을 모두 삽입하고 스택이 empty가 아닐 경우 스택에서 원소를 꺼내 그 노드의 인접노드들을 다시 삽입한다. 후입선출인 스택의 구조를 이용해 넣고 꺼내다보면 깊이우선 탐색을 완료할 수 있다. 

 

 

---

트리와 쿼리 성공

문제

간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.

• 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.

만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자.

입력

트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)

이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)

이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다.

이어 Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N)

입력으로 주어지는 트리는 항상 올바른 트리임이 보장된다.

---

 

서브트리의 노드 수를 세어야하기 때문에 깊이 우선 탐색을 사용해야 겠다고 생각했다.

서브트리속 정점의 수는 [ 해당 부모노드 서브트리에 속한 정점 수+= 자식노드의 서브트리 수 ] 형태로 볼 수 있다. 

 

dfs return에서 서브트리의 사이즈를 반환하게 된다. 

따라서 트리의 사이즈 += dfs(자식노드)로 구성해주면 반환되는 자식노드의 서브트리에 속한 노드 수가 더해진다. 

 

int dfs(int start) {
	visited[start] = 1;
	for (int i = 0; i < tree[start].size(); i++) {
		int next = tree[start][i];
		if (!visited[next]) {
			t_size[start]+=dfs(next);
		}
	}
	return t_size[start];//서브트리 사이즈 return 
}