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

---

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• BFS
• DFS

---

문제 설명

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

---

입력 설명

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

---

출력 설명

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

---

예제 입력

7
1 6
6 3
3 5
4 1
2 4
4 7

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

---

예제 출력

4
6
1
3
1
4

1
1
2
3
3
4
4
5
5
6
6

---

아이디어

입력받은 값으로 그래프를 만든다.

BFS로 그래프를 순회하면서 자신의 부모 노드를 기록하는 배열에 부모 노드를 기록한다.

이후 2~n번의 부모 노드를 모두 출력한다.

---

알고리즘

입력 받은 값으로 그래프를 만든다.

BFS로 그래프를 순회하면서 자신의 부모 노드를 기록하는 배열에 값이 0이라면

 자신의 부모 노드를 기록하고 BFS를 돌기 위한 queue에 자신을 넣는다.

BFS 순회가 끝나면 2~n번의 부모 노드 기록 배열의 값을 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <list>
using namespace std;
int n;
void BFS(vector<vector<int>> &vec)
{
	list<int> li;
	vector<int> ans(n+1,0);
	li.push_back(1);
	ans[1] = 1;
	while(!li.empty())
	{
		int bef = li.front();
		li.pop_front();
		for(auto &a: vec[bef])
		{
			if(ans[a] == 0)
			{
				li.push_back(a);
				ans[a] = bef;
			}
		}
	}
	for(int i=2; i<=n; i++)
		cout<<ans[i]<<"\n";
}
int main()
{
	cin>>n;
	vector<vector<int>> vec(n+1);
	for(int i=0,a,b; i<n-1; i++)
	{
		cin>>a>>b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	BFS(vec);
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/11725

1차 시도 : 처음에는 단순히 1차원 배열만을 사용하는 방법으로 시도, 주어지는 노드가 연결되어 있지 않은 경우가 있어서 실패

 

2차 시도 : 연결되어 있지 않은 노드가 주어질 경우 list에 임시로 저장해 놓고 모든 입력을 다 받은 후 list에 남은 노드들을 처리하는 방법으로 시도, 역순으로 주어질 경우 n(n-1)/2만큼 걸리므로 시간초과

 

3차 시도 : 정석적인 BFS를 사용하는 방법으로 시도, 성공

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!