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

풀이

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
vector<int> a[100001];
bool check[100001];
int parent[100001];
	
int main() {
	int n;
	cin >> n;
	queue<int> q;
	for (int i=0; i<n-1; i++) {	// 입력을 2차원 배열에 저장
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	check[1] = true;
	parent[1] = 0;
	q.push(1);	// 루트인 1부터 dfs 시작
	while (!q.empty()) {
		int x = q.front();
		q.pop();
			for (int y : a[x]) {
				if (check[y] == false) {
					check[y] = true;
					parent[y] = x;
					q.push(y);
			}
		}
	}
    for (int i=2; i<=n; i++) {
        cout <<parent[i] << '\n';
    }	
	return 0;
}

개념

 

트리의 부모를 찾기 위해 BFS 방식을 사용한다.

이 방식은 루트에서 자식으로 퍼져나가는 것을 구현하기에 유리하다.

왼쪽: 트리  오른쪽: 큐

 

---

범위 기반 for문을 활용한다.

보통 for ( int x : array ) 이런 식으로 사용해서, array 배열의 원소가 없을 때까지 반복한다. 

하지만 풀이에서는 for ( int y : a[x] ) 로 나타냈다.

이는 간선 리스트 a[x]에 연결된 a[x][0], a[x][1] 등이 존재할 때까지 반복하는 문장이다.

---

풀이

 

입력은 이전에 그래프의 간선 리스트를 입력받는 방식과 똑같이 받는다.

간선리스트 입력된 모습

dfs와 달리, bfs는 노드를 큐에 저장하며 한 노드에 연결된 노드들을 먼저 방문한다.

문제의 조건에 따르면 무조건 1이 루트이다.

따라서 bfs를 1부터 실시해서 차례대로 트리를 내려가면서 parent 배열의 index에 부모 값을 저장하면 된다.

 

※ parent[y] = x

이 문장이 부모와 자식을 잘 구분해 저장할까 의문이 들었다.

dfs가 진행되는 순서를 생각하면 의문이 풀린다.

 

큐에 저장된 x 값을 통해, y의 노드를 방문한다.

이 진행은 트리가 내려오는 것과 동일하므로 부모와 자식이 섞이지 않는다.

 

---

+a

틀린풀이

#include <iostream>

using namespace std;

int main() {
	int a[100001];
	int n;
	cin >> n;
	for (int i=1; i<n; i++) {
		int x, y;
		cin >> x >> y;
		if (x == 1) {
			a[y] = x;
		}
		else if (a[x]!= 0) {
			a[y] = x;
		}
		else {
			a[x] = y;
		}
	}
	for (int i=2; i<=n; i++) {
		cout << a[i] << '\n';
	}
	return 0;
}

문제를 좀 더 단순하게 생각하고 접근했다.

이 코드를 통해 주어진 예제는 모두 해결가능하다.

 

하지만 예외가 발생한다.

그 이유는 이 풀이는 입력이 나타나는 방식에 너무 의존하기 때문인 것 같다.

또한 위 방식대로 진행하면 1을 반드시 루트로 만들어주지 않는다.