[백준 알고리즘 c++] 문제 44.트리의 부모 찾기 11725

알고리즘

 

[문제]

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

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

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

 

[나의 풀이]

문제
1. 트리의 루트를 1이라고 정했을때 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
1. 노드의 개수 N을 입력 받는다.
2. n-1개의 간선을 연결할 정점이 주어진다.
 처리
1.bfs 방식으로 모든 노드가 정점의 위치를 가지도록 설정함

 

[소스 코드]

 

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

using namespace std;
vector<int> graph[100001];
bool isVisited[100001] = { false };
int check[100001] = { 0 };

void bfs()
{
	queue<int> que;
	que.push(1);
	isVisited[1] = true;

	while (!que.empty())
	{
		int node = que.front();
		que.pop();

		//자식노드에 부모노드 박아주면됨
		for (int newNode : graph[node])
		{
			if (isVisited[newNode] == false)
			{
				check[newNode] = node;
				isVisited[newNode] = true;
				que.push(newNode);
			}
		}
	}


}

int main()
{
	//
	// 문제
	// 1. 트리의 루트를 1이라고 정했을때 각 노드의 부모를 구하는 프로그램을 작성하시오.
	// 입력
	// 1. 노드의 개수 N을 입력 받는다.
	// 2. n-1개의 간선을 연결할 정점이 주어진다.
	// 처리
	// 1.bfs 방식으로 모든 노드가 정점의 위치를 가지도록 설정함
	// 출력
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N = 0;
	cin >> N;

	for (int i = 0; i < N - 1; i++)
	{
		int x = 0;
		int y = 0;
		cin >> x;
		cin >> y;
		graph[y].push_back(x);
		graph[x].push_back(y);
	}

	bfs();

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

	return 0;
}

문제점 : 트리의 경우 사이클이 없고 부모노드를 1개만 가진다는 특성을 이해해야 한다.

다른 풀이 dfs)

#include <iostream>
#include <vector>

using namespace std;
#define MAX 100001

int N;
int arr[MAX];
bool visited[MAX];
vector<int> v[MAX];

void dfs(int k) {
    visited[k]=true;
    for(int i=0;i<v[k].size();i++) {
        int next = v[k][i];
        if(!visited[next]) {
            arr[next]=k;
            dfs(next);
        }
    }
}

int main() {
    cin >> N;

    for(int i=0;i<N;i++) {
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1);

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

[피드백]