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

백준 11725번: 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

---

문제 설명

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

---

입력과 출력

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

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

---

접근 방법

이번 문제는 정수 N을 입력받고, N개의 노드가 있는 트리를 그래프 만들듯이 각 노드들을 연결하며 만든다. 이후 이렇게 만들어진 트리에서 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력하는 문제다.

문제가 그래프처럼 트리를 만들었기때문에 문제 진행도 그래프처럼 2차원 배열을 사용해서 진행했다. 출력의 경우 간단하게 DFS 처럼 인접하는 노드를 배열에 저장하고 출력하면 해결할 수 있다.

참고로 처음에는 일반적인 2차원 배열을 사용해서 진행하려 했는데 아무래도 N이 10만이라는 큰 숫자까지 되다보니, 크기가 너무 커서 stl vector를 사용해서 해결했다. 개인적으로 STL은 stack과 queue만 사용해봤어서 vector는 인터넷에서 조금 찾아보고 사용했다.

https://coding-factory.tistory.com/596

[C++] STL Vector 사용법 & 예제 총정리

---

코드

#include <stdio.h>
#include <vector>
#define MAX 100001

using namespace std;

vector<int> tree[MAX];
int root[MAX];

void printRoot(int N, int root[]) {
	for (int i = 2; i <= N; i++)
		printf("%d\n", root[i]);
}

void DFS(int a) {
	for (int i = 0; i < tree[a].size(); i++) {
		int j = tree[a][i];

		if (root[j] == 0) {
			root[j] = a;
			DFS(j);
		}
	}
}

int main(int argc, char*argv[]) {
	int N, a, b;

	scanf("%d", &N);

	for (int i = 0; i < N - 1; i++) {
		scanf("%d %d", &a, &b);
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

	DFS(1);

	printRoot(N, root);

	return 0;
}

---

결과

백준 제출 결과