[c++] 백준 11725 - 트리의 부모 찾기(BFS)

0. [c++] 백준  -

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

1. 풀이

처음에 상당히 고생을 했다. 기저사례를 넣어 이미 부모가 있는 node는 빼고 계산하고, 또, 전체를 괜히 다시 반복하기도 하는 등의 코드들을 만들었었는데, 완성을 하고보니 너무 간단하게 구현이 되어버렸다.

뭔가 노력을 한게 억울한 느낌이 들 정도의 코드라 허무한 느낌도 없지않아 들었다.

다음에 이와 비슷한 문제가 나오면 고생하지 않고 풀고싶다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include<iostream> #include<vector>   using namespace std;   //부모 노드가 들어가도록 설계하자. int treeNodeMother[100001]; vector<int> arr[100001];   //pair배열을 모두 순회하면서 부모 노드를 찾는다. 만일 양쪽의 부모가 모두 결정되어있지 않는다면 양쪽을 모두 깊이탐색을 한다. //만일 끝까지 찾아도 나오지 않는다면 자신이 부모 노드인 것이고, 모두 차례대로 부모노드가 되도록 설계해주고, //위에서 부모 노드가 나오면 또 그쪽대로 부모노드를 연결해준다. void connectMotherNode(int node = 1) {     //1부터 탐색을 하므로 첫 시작은 자동으로 부모 노드이다.     //이와 연결되어있는 수들 (arr[1])의 부모 노드를 1로 해준다.     //이후, 다시 그 수로 들어가 부모 노드를 찾아준다.     for (int i = 0; i < arr[node].size(); i++) {         if (treeNodeMother[arr[node][i]] == 0) {             treeNodeMother[arr[node][i]] = node;             connectMotherNode(arr[node][i]);         }     } }     int main() {     int N;     int a, b;     cin >> N;     treeNodeMother[1] = 1;       for (int i = 1; i < N; i++) {         cin >> a >> b;         arr[a].push_back(b); arr[b].push_back(a);     }       connectMotherNode();       for (int i = 2; i <= N; i++) {         cout << treeNodeMother[i] << "\n";     } } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!