[ 백준 11725 ] 트리의 부모 찾기 (C++)

 

 

11725번: 트리의 부모 찾기

 

 

문제!

---

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

---

간단하네요....

 

루트노드가 1일때

단순히 연결된 노드들의 쌍을 입력받으면 각 노드의 부모를 출력하면 되는 문제!

 

 

여기서 가장중요한 부분은 연결된 쌍만가지고 어떻게 트리를 구성해야하나.....

 

 

저는여기서 bfs탐색을 이용해 보기로 했습니다. 

 

루트노드인 1번 노드부터 차례대로 연결된 노드들을 탐색하는 방법!

그러기위해서 다음과 같은 과정을 거쳐야합니다.

1. 연결된 쌍에 대해서 저장

2. 부모를 찾을때 마다 체킹!

 

 

 

그럼 바로!

 

 

코드!

---

먼저 선언부

 

트리의 부모와 연결된 노드에 대해 기록할 벡터 두개를 선언해줍시다.

#define INF 987654321
int N; // 트리의 루트는 1

vector<int>pre(100001, INF);// 번호에 대한 부모
vector<int>con[100001];// 번호에 대해 연결된것들

 

기본적인 입력을 받아줍시다.

int main() {

pre[1] = 0;

cin >> N;

for (int i = 0; i < N-1; i++) {
    int temp1, temp2;
    cin >> temp1 >> temp2;

    con[temp1].push_back(temp2);
    con[temp2].push_back(temp1);
}

연결쌍을 저장할땐 양방향으로! (어디가 부모인지 모르기에)

 

 

 

다음은 bfs 구현부분입니다. 

int tempInd = 1;
queue<int> Templist;

Templist.push(1);


while (!Templist.empty()) {
    tempInd = Templist.front();
    Templist.pop();


    for (int j = 0; j < con[tempInd].size(); j++) {
        int saveInd = con[tempInd][j];
        if (pre[saveInd] == INF) {
            pre[saveInd] = tempInd;
            Templist.push(saveInd);
        }
    }
}

Templist에 계속해서 연결된 노드들을 추가해주며 부모를 설정하는 방식입니다.

 >>> 만약 이미 부모가 설정되어 있다면?   뛰어 넘겨 주어야합니다. 

>>>> 부모가 2개인 경우는 없습니다. 2개가 되는 순간 사이클이 발생해 트리가 아닌 그래프가 되기 때문!

 

 

 

 

처음엔 bfs인지 모르고 구현하다  보니 bfs 구조가 되어버렸네요;;

 

 

여기까지가 끝!

 

그리고.....

출력부

for (int i = 2; i <= N; i++) {
		cout << pre[i] << "\n";  /// endl; 사용하면 시간초과남
	}

endl; 자제 해야 겠네요

 

 

 

 

 

이번 문제를 통해 배운 내용

1. bfs 다시 복습

2. endl; 자제하기

 

 

 

ALL

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <deque>
#include <queue>
#include <deque>


using namespace std;

#define INF 987654321
int N; // 트리의 루트는 1

vector<int>pre(100001, INF);// 번호에 대한 부모
vector<int>con[100001];// 번호에 대해 연결된것들


int main() {

	pre[1] = 0;

	cin >> N;

	for (int i = 0; i < N-1; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;

		con[temp1].push_back(temp2);
		con[temp2].push_back(temp1);
	}

	int tempInd = 1;
	queue<int> Templist;

	Templist.push(1);


	while (!Templist.empty()) {
		tempInd = Templist.front();
		Templist.pop();


		for (int j = 0; j < con[tempInd].size(); j++) {
			int saveInd = con[tempInd][j];
			if (pre[saveInd] == INF) {
				pre[saveInd] = tempInd;
				Templist.push(saveInd);
			}
		}
	}

	for (int i = 2; i <= N; i++) {
		cout << pre[i] << "\n";
	}



	return 0;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!