c++ 11725 트리의 부모 찾기 (백준)

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	int n, a, b;
	cin >> n;
	
	vector<int> vec[n+1]; //간선들을 저장할 벡터들
	queue<pair<int, int> > q; //BFS을 위한 큐
	bool v[n+1]; //방문했는가?
	int ans[n+1]; //부모노드 저장
    
    memset(v, false, sizeof(v)); //v을 전부 false로 초기화
	
	for(int i=2; i<=n; i++) { //간선 n-1 만큼 입력받기
		cin >> a >> b;
		vec[a].emplace_back(b);
		vec[b].emplace_back(a);
	} 
	
    //root 는 1
	for(int i : vec[1]) q.push({1, i}); //큐에 간선에 1이 포함된 것을 집어넣기 
	v[1] = true;
	
    //BFS
	while(!q.empty()) {
    	//큐에서 하나를 꺼내 변수에 저장
		int x = q.front().first;
		int y = q.front().second;
	
		v[y] = true; //방문했음 처리
		ans[y] = x; //y의 부모노드는 x이다.
		for(int i : vec[y]) if(!v[i]) q.push({y, i}); //자식노드가 방문하지 않았다면, 큐에 삽입
		
		q.pop(); //사용한 데이터를 큐에서 제거합니다.
	}
	
	for(int i=2; i<=n; i++) cout << ans[i] << '\n'; //2~n번의 노드들의 부모들을 출력합니다.
}

 

풀이 : BFS

 

1. 간선들을 입력받으면, 이를 각각의 벡터에 저장합니다.

ex 4 5

vec[4] 에 5 을 넣고

vec[5] 에 4 을 넣습니다.

 

둘 다 넣는 이유는, 어디가 부모이고 어디가 자식인지를 모르기 때문입니다.

 

2. pair<int, int>형태로 데이터를 저장하는 큐를 만든다음 간선에 1이 포함된 간선들을 (즉 vec[1]의 내용들을) 큐에 삽입합니다. 그런다음 노드 1은 방문처리 합니다.

 

3. BFS 입니다.

큐에서 하나를 꺼내면, first는 간선의 부모, second는 간선의 자식이 됩니다. 자식의 방문처리를 해주고, 자식의 부모노드를 저장하는 배열에 부모의 값을 대입합니다. 그런 다음 자식이 부모가 되는 간선들 중, 아직 방문하지 않은 노드와 연결되 있는 간선들을 큐에 새롭게 집어 넣습니다. 마지막으로 처음에 사용했던 데이터를 큐에서 제거합니다

 이 과정을 큐가 비워질 때까지 반복합니다.

 

4. 2~n번 노드의 부모노드를 차례차례 출력합니다.

 

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

11725번: 트리의 부모 찾기