[알고리즘] 백준 11725번: 트리의 부모 찾기 (C++), 2차원 동적 배열 (vector)

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

11725번: 트리의 부모 찾기

처음 문제를 봤을 때는 행과 열이 둘 다 100,001인 bool 2차원 배열을 선언해서 두 노드가 주어지면 간선을 1로 바꿔주어서 각 행을 DFS를 돌리면 될 거라고 생각했다. 하지만, 이럴 경우 배열의 크기가 너무 커서 오류가 나게 된다.

 

여기서 알아냈던 게 vector의 2차원 동적 기능(?)이었다.

기존 1차원 vector배열에서 push_back을 이용하는 것은 늘 사용했지만 2차원에서 사용할 방법은 생각도 못 해봤다.

각 행에 push가 가능하다는 뜻이다.

// 선언
vector<int> tree[MAX];
// push_back
tree[n1].push_back(n2);

vector가 동적인 것은 알았지만 이렇게까지 동적일 줄은 몰랐다.

---

솔루션

• 루트 노드가 1이기에 1부터 DFS를 시작한다.
• DFS의 시작에 해당 노드의 방문을 체크한다. >> DFS 할 때 부모 노드를 탐지하지 않기 위해
• tree 배열의 행에서 존재하는 열의 방문 여부를 확인하고 방문하지 않았다면 그에 해당하는 행을 parent로 알려준다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 100001

int n;
vector<int> tree[MAX];
bool visited[MAX];
int parent[MAX];

void dfs(int k) {
	visited[k] = 1;
	for (int i = 0; i < tree[k].size(); i++) {
		int next = tree[k][i];
		if (!visited[next]) {
			parent[next] = k;
			dfs(next);
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		int n1, n2;
		cin >> n1 >> n2;
		tree[n1].push_back(n2);
		tree[n2].push_back(n1);
	}

	dfs(1);

	for (int i = 2; i <= n; i++) {
		cout << parent[i] << '\n';
	}

	return 0;
}

---

vector의 새로운 기능(?)을 알게 되었다. 배열의 크기에 있어서 새로운 생각을 할 수 있게 되었던 거 같다.

업 솔빙 한 번 해보면 더 좋을 거 같다.