C++ / 11725 / 트리의 부모 찾기 ( 깊이 우선 탐색 )

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

문제 요약

루트가 없는 트리가 주어집니다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구해야 합니다.

문제 풀이

1. 입력에 필요한 백터와 부모 노드를 저장할 배열 방문체크 배열을 100004의 크기로 만듭니다. ( 배열은 100000보다 작게 만들면 백준에서 out of bounds 오류가 발생할 수 있습니다. )

2. 예외 처리를 해주고 입력을 받습니다. 한 번에 2개의 숫자를 입력받는데 트리 이기 때문에 부모자식은  서로서로 연결되게 합니다.

3. dfs함수를 만드는데, 기존 dfs와 다르게 부모 노드를 저장하게 해야합니다. x의 인접노드를 탐색하는게 dfs의 기본 로직인데 이를 뒤집어 보면 x는 자식을 가지고 있는 부모 노드라고 볼 수 있습니다.

4. x를 부모 노드 배열에 자식 노드의 번호 인덱스에 넣어줍니다.

5. 메인함수에서 부모 노드 배열을 2번째 노드부터 출력합니다.

주의할 점

위에도 언급이 되어있지만 배열들의 크기를 100000보다  크게 하지 않으면 백준에서 out of bounds오류가 발생 할 수 있습니다.

반복문과 재귀함수를 사용하기 때문에 시간 초과가 나기 쉽습니다.

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

위에 코드를 사용하여 입출력 연산의 소요 시간을 줄여주었습니다.

코드

#include<iostream>
#include<vector>

using namespace std;

int n;

vector<int>v[100004];
int p[100004];
bool visited[100004];

void dfs(int x)
{
	// 방문한 노드면 true
	visited[x] = true;
	for (int i : v[x])
	{
		// i에는 자식 노드 x에는 그 자식의 부모 노드가 들어있음
		if (!visited[i])
		{
			// 부모 노드를 저장할 배열에 자식 노드 i 인덱스에 저장
			p[i] = x;
			// 그 다음 자식의 자식노드를 찾음 
			dfs(i);
		}
	}
}
int main()
{

	cin >> n;
	if (n < 2 || n > 100000)
	{
		return 0;
	}
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	dfs(1);
	// 2번째 노드부터 출력해야함
	for (int i = 2; i <= n; i++)
	{
		cout << p[i] << "\n";
	}
	return 0;
}

반응형

예제 1

7
1 6
6 3
3 5
4 1
2 4
4 7

결과 1

예제 2

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

결과 2