[백준 11725번 C/C++] 트리의 부모 찾기

 

[백준 11725번 C/C++] 트리의 부모 찾기

 

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

11725번: 트리의 부모 찾기

---

 

해결전략

 

트리 Tree

너비우선탐색 BFS

 

	vector<int> v[  ]
v[1]	6, 4
v[2]	4
v[3]	6, 5
v[4]	1, 2, 7
v[5]	3
v[6]	1, 3
v[7]	7

 

 

Q
1	6	4	3	2	7	...

 

---

 

정답 코드

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n;
vector<vector<int>> v(100001); // 각 노드의 연결정보를 저장할 2차원 벡터
// vector<int> v[100001]; // 위와 같다. 표기 차이
int ch[100001]; // 방문 여부를 체크할 배열
int tree[100001]; // 부모 노드 정보를 저장할 배열

void BFS()
{
	queue<int> Q;
	Q.push(1); // 루트 노드인 1부터 탐색 시작
	ch[1] = 1; // 루트 노드 방문 표시

	while(!Q.empty())
	{
		int parent = Q.front(); // 현재 탐색 중인 노드를 parent로 설정
		Q.pop();

		for(int i = 0; i < v[parent].size(); i++) // 현재 노드와 연결된 모든 노드를 탐색
		{
			int child = v[parent][i]; // 연결된 노드를 child로 설정

			if(ch[child] == 0)
			{
				tree[child] = parent; // child의 부모 노드를 parent로 설정
				Q.push(child);
				ch[child] = 1;
			}
		}
	}
}

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

	cin >> n;
	int a, b;
	for(int i = 0; i < n-1; i++){
		cin >> a >> b;
		v[a].push_back(b); // 양방향으로 연결 정보를 저장
		v[b].push_back(a);
	}

	BFS();

	for(int i = 2; i <= n; i++){
		cout << tree[i] << "\n"; // 각 노드의 부모 노드 번호를 출력
	}

	return 0;
}

 

---

 

 

 

 

 

 

 

 

---