[백준] 3584번 - 가장 가까운 공통 조상 (C++) 문제 및 풀이

문제) 백준 - 트리/DFS - 가장 가까운 공통 조상

https://www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

 

DFS를 통해 한 노드에 대하여 조상으로 올라가 트리를 순회하여 Set에 모든 조상을 저장합니다. 그 후, 공통 조상을 탐색할 다음 노드에 대하여 마찬가지로 트리를 순회합니다. 이때 탐색한 조상이 Set에 있을 경우, 그 조상을 반환하여 출력합니다.

 

C++ 소스코드)

	void dfs(int now){
	visited[now] = true;
	st.insert(now);
	for(int next:graph[now])
	if(!visited[next])
	dfs(next);
	}
	int dfs2(int now){
	visited[now] = true;
	if(st.find(now) != st.end())
	return now;
	for(int next: graph[now])
	if(!visited[next])
	return dfs2(next);
	}
	int solve(int a, int b){
	st.clear();
	memset(visited, false, sizeof(visited));
	dfs(a);
	memset(visited, false, sizeof(visited));
	return dfs2(b);
	}

view raw 3584.cpp hosted with ❤ by GitHub

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/3584_%EA%B0%80%EC%9E%A5%EA%B0%80%EA%B9%8C%EC%9A%B4%EA%B3%B5%ED%86%B5%EC%A1%B0%EC%83%81.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions