[BOJ, 백준 알고리즘]11725번 문제/ 트리의 부모찾기

문제

문제 링크    

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

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

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

접근방향

문제에서 주목해야 할 것이 주어진 구조가 트리라는 것이다. 나의 경우 이진트리를 먼저 공부하였기 때문에 무의식적으로 이진 트리를 떠올려 이진트리라고 가정을 하다가 한참을 헤메었다. 이 문제에서의 트리의 경우 자식이 3개 이상이 될 수도 있는 등 이진트리의 성질을 만족하지 않는 케이스까지 고려해야 했기 때문에 이진트리에서의 방식을 쓰기에는 어렵다. 따라서 트리 또한 그래프의 일종이라고 생각하고 트리가 아닌 그래프를 구현하여 문제를 풀어나갔다. 그래프로 놓고 풀어보니 너무 간단하게 풀려서 허탈할 정도였다.

풀이

이 문제의 경우 노드의 개수가 10만개까지 있으므로 배열을 통해 그래프를 구현하면 메모리 초과가 뜰 것으로 보고 연결 리스트를 사용했다.

문제 풀이의 절차는 다음과 같다.

1. 연결된 노드의 값들을 저장하는 벡터와 자신의 값을 가지는 노드를 생성한다.
2. 주어진 입력을 바탕으로 그래프를 생성한다.
3. 생성된 그래프를 BFS, 혹은 DFS를 이용해 탐색한다.(여기서는 BFS 사용)
   1. 각 노드의 부모 노드의 값을 저장하는 벡터 parents를 생성한다. 부모 노드의 값은 루트 노드를 제외하고 모두 -1로 초기화한다.

      (부모 노드의 값이 -1이면 그 노드를 방문하지 않았다고 간주한다.)

   2. 탐색을 위해 노드를 저장하는 큐를 생성하고 루트 노드의 값이 1로 정해졌으므로 그 노드를 enqueue한다.
   3. 큐의 가장 앞에 있는 노드를 방문한 뒤 임시노드 ref에 저장하고 dequeue를 해준다.
   4. 큐의 가장 앞에 있는 노드의 값이 그 노드와 연결 된 노드들의 부모 값이다.
   5. 만약 부모 노드의 값이 -1로 되어 있으면 ref노드의 값을 부모값으로 지정하고

      (parents의 지정된 인덱스에 부모 노드의 값을 저장)

      그 노드를 enqueue해준다.

      그렇지 않으면 건너뛴다.

   6. 이 과정을 큐가 빌 때까지 반복한다.
4. 위 과정을 거치면 parents 벡터에 각 노드의 부모 노드의 값이 저장된다.

소스 코드

#include <iostream>
#include <vector>
using namespace std;

// 그래프를 이루는 노드
typedef struct node{
	vector<int> next;
	int value;
}node;

vector<int> find_parent(vector<node*> tree){
	
	vector<node*> node_vec;
	vector<int> parents;
    
    // 부모 노드의 정보 담는 parents 벡터 초기화
	parents.resize(tree.size(),-1);
	parents[1]=1;
    
    // BFS 시행
	node* ref= tree[1];
	node_vec.push_back(ref);
	while(!node_vec.empty()){
    	// 큐에 삽입된 노드를 방문한 뒤 임시 노드에 저장하고 dequeue
		ref = node_vec.front();
		node_vec.erase(node_vec.begin());
		for(int i=0;i<ref->next.size();i++){
        	// 연결된 노드가 방문하지 않았던 노드일시 큐에 삽입하고 parent 벡터에 부모값 저장
			if(parents[ref->next[i]]==-1){
			node_vec.push_back(tree[ref->next[i]]);
			parents[ref->next[i]]=ref->value;
			}
		}
	}
	return parents;
}


int main() {
	vector<node*> tree;
	int num=0;
	int n_1=0, n_2=0;
	scanf("%d",&num);
	getchar();
	// 트리 초기화
	for(int i=0;i<=num;i++){
		node* new_n;
		new_n=(node*)calloc(1,sizeof(node));
		new_n->value= -1;
		tree.push_back(new_n);
	}
	// 입력값에 따라 그래프를 생성
	for(int i=0;i<num-1;i++){
		scanf("%d %d",&n_1,&n_2);
        getchar();
		if(tree[n_1]->value==-1){tree[n_1]->value=n_1;}
		if(tree[n_2]->value==-1){tree[n_2]->value=n_2;}
		tree[n_1]->next.push_back(n_2);
		tree[n_2]->next.push_back(n_1);
	}
    
    // 결과값을 출력
    vector<int> answer = find_parent(tree);
	for(int i=2;i<tree.size();i++){
		printf("%d\n",answer[i]);
	}
	return 0;
}