백준 3584 c++ "가장 가까운 공통 조상" -PlusUltraCode-

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

[필자 사고]

최소 공통 조상 문제다.

핵심은 부모를 기록하는 과정이다. 

자신의 parent[child] = 부모  저장형태로 배열을 만들게 되면 

그 이후의 2가지 값이 들어오면 최소 공통 조상을 찾는 과정은 쉽다. 

해당 배열을 이용하여 계속 부모로 올라가다 보면 처음 root 노드로 도달하게 된다. 

다른 작업도 위와 같이 반복하다 방문했던 흔적을 먼저 발견한 곳이 최소 공통 조상이 된다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

프로그램의 전체 구조

• 여러 개의 테스트 케이스가 주어진다.
• 각 테스트 케이스마다 트리 구조가 입력으로 들어오고, 두 노드가 주어지면 두 노드의 가장 가까운 공통 조상을 찾아 출력한다.

---

처리 과정

1. 초기화 단계
   • 트리의 노드 개수를 입력받는다.
   • 각 노드의 부모를 저장할 배열과 방문 여부를 기록할 배열을 준비한다.
2. 트리 구성 단계
   • 입력으로 부모와 자식 관계가 주어진다.
   • 이를 이용해 “이 노드의 부모는 누구인지”를 기록한다.
   • 이 과정을 통해 각 노드에서 부모 노드로 거슬러 올라갈 수 있는 구조가 완성된다.
3. 첫 번째 노드의 경로 기록
   • 첫 번째로 주어진 노드에서 시작해 루트까지 거슬러 올라간다.
   • 지나가는 모든 조상 노드를 방문했다고 표시한다.
   • 이렇게 하면 첫 번째 노드의 모든 조상 집합이 기록된다.
4. 두 번째 노드에서 공통 조상 찾기
   • 두 번째 노드에서 시작해 역시 루트까지 거슬러 올라간다.
   • 올라가는 도중에 이미 방문 표시가 되어 있는 노드를 만나면, 그 노드가 두 노드의 공통 조상이다.
   • 가장 먼저 만나는 노드가 곧 두 노드의 가장 가까운 공통 조상이다.
5. 출력 단계
   • 찾은 공통 조상을 출력한다.
   • 다음 테스트 케이스가 있다면 동일한 과정을 반복한다.

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int T;
int main(void) {
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		vector<int> parent;
		vector<bool> visited;
		parent.assign(N + 1,0);
		visited.assign(N + 1, 0);

		for (int i = 0; i < N - 1; i++) {
			int parentNum, child;
			cin >> parentNum >> child;

			parent[child] = parentNum;
		}

		int x, y;
		cin >> x >> y;
		while (x != 0) {
			visited[x] = true;
			x = parent[x];
		}

		while (y != 0) {
			if (visited[y]) {
				cout << y << "\n";
				break;
			}
			y = parent[y];
		}
	}
}