백준 11725 c++ "트리의 부모 찾기" -PlusUltraCode-

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

 

 

 

[필자 사고]

트리의 부모를 찾으라는 문제이다.

DFS탐색을 이용하여 방문하기 직전에 parentNode[next] = now; 와 같은 코드를 작성하여

다음 노드의 부모를 미리 저장하는 방식으로 문제를 해결해 나갔다.

 

아래는 소스코드 해설이다.

 

1. Input 함수:

여기서 우리는 큐(myQueue)를 준비하여 목표 노드에서 출발합니다. 이 목표 노드는 트리의 루트 노드인 1번 노드가 됩니다. 입력으로 주어지는 start와 end는 각 노드 간의 연결을 나타내며, 이 연결 정보를 바탕으로 노드들 간의 경로를 큐에 저장합니다. 각 노드는 자신과 연결된 노드를 가리키는 정보를 arr라는 큐에 차곡차곡 쌓아둡니다.

2. DFS 함수:

목표 노드에서 출발하여 탐색을 시작합니다. 우선, 탐색을 진행하기 전에 현재 노드가 이미 방문되었는지 확인합니다. 만약 방문된 적이 없다면, 큐에서 start 노드를 꺼내어 해당 노드로부터 연결된 다른 노드들로 이동합니다.

탐색 중에 "이동 가능한 경로"를 찾으면, 즉 다음 노드를 방문할 수 있다면 그 노드의 부모 노드를 현재 노드로 설정합니다. 이것은 "현재 도착한 노드가 최장 시간일 때만 이동한다"는 개념으로 설명될 수 있습니다. 즉, 현재 노드에서 새로운 경로로 이동할 수 있다면 그 경로로 이동하여 부모 자식 관계를 설정합니다.

이렇게 탐색이 끝날 때까지 큐의 경로를 따라 이동하며, 각 노드의 부모 노드를 기록합니다.

3. GameStart 함수:

DFS가 끝난 후, 큐에서 이동한 경로를 기반으로 각 노드의 부모 노드가 어떻게 설정되었는지를 확인하는 단계입니다. 여기서는 목표 노드(1번)에서 시작하여 최장 경로로 연결된 노드들을 하나씩 확인하고, 2번 노드부터 N번 노드까지의 부모 노드를 출력합니다

 

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> arr;
vector<int> parentNode;
vector<bool> visited;
int N;

void Input() {
	cin >> N;
	arr.resize(N + 1);
	parentNode.resize(N + 1);
	visited.resize(N + 1);

	for (int i = 0; i < N; i++) {
		int start, end;
		cin >> start >> end;
		arr[start].push_back(end);
		arr[end].push_back(start);
	}
}

void DFS(int start) {
	if (visited[start])return;
	
	visited[start] = true;

	for (int next : arr[start]) {
		if (visited[next] == false) {
			parentNode[next] = start;
			DFS(next);
		}
	}
}


void GameStart() {
	DFS(1);

	for (int i = 2; i <= N; i++) {
		cout << parentNode[i] << '\n';
	}
}

int main(void) {
	Input();
	GameStart();
}