[백준/C++] 가장 가까운 공통 조상_3584

📝 문제

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

💻 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int arr[10001];
bool visited[10001];
int t, parent, child, n, a, b;

void dfs(int child) {

	visited[child] = true;
	if (arr[child] == 0) {	// 부모가 없다.
		return;
	}
    ** // visited[child] = true; **
	dfs(arr[child]);
}

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

	cin >> t;

	while (t--) {
		cin >> n;

		memset(arr, 0, sizeof(arr));
		memset(visited, false, sizeof(visited));

		for (int j = 0; j < n - 1; j++) {
			cin >> parent >> child;
			arr[child] = parent;
		}

		cin >> a >> b;

		dfs(a);
		while (true)
		{
			if (visited[b])	// 조상에 해당하는가?
			{
				cout << b << '\n';
				break;
			}
			b = arr[b];	// 부모로 올라감
		}
	}

	return 0;
}

📌 해결방법

1. 자식의 조상 그래프 배열로 구현
2. 공통 노드 1개를 dfs 돌려서 조상을 체크
3. 나머지 공통 노드 역시 dfs를 돌려 체크된 조상 확인

✔ 느낀 점

처음 문제를 봤을 땐 쉬워보였는데, 별의 별 오류를 다 경험하게 되었다.
출력 초과는 백준 풀면서 처음 봤는데 찾아보니 답이 3개일 때 3개 출력이 아니라서 발생하는 오류라고 한다(???)
그래서 for문 테케를 while(t--)로 고쳤더니 틀렸다로 나왔다ㅎㅎ...
시간초과는 visited를 제일 먼저 안해줘서 발생했다.
코드를 제대로 구현한 것 같아도 하나하나 뜯어보면 결국 내가 문제였다는 교훈을 얻었다...