[백준/C++] 11725 트리의 부모 찾기

유형	난이도	완료일	링크	특이사항
백트래킹	실버2	23/04/03	https://www.acmicpc.net/problem/11725

 

내 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> vv;
vector<int> v;
int v1, v2;
int arr[100001];
int visited[100001];
int n;

void DFS(int parent, int me)
{
	arr[me] = parent;
	visited[me] = 1;
	
	for(int i=0; i < vv[me].size(); i++)
	{
		if(visited[vv[me][i]]==1)
			continue;
		
		DFS(me, vv[me][i]);
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	cin >> n;
	
	
	for( int i =0; i <= n; i++)
	{
		vv.emplace_back(v);
	}
	
	for(int i = 1; i <= n-1; i++)
	{
		cin >> v1 >> v2;
		vv[v1].emplace_back(v2);
		vv[v2].emplace_back(v1);
	}
	
	
	DFS(0,1);
	
	for(int i=2;i<=n;i++)
		cout<< arr[i] <<"\\n";
}

  방향이 주어지지 않은 트리에서 1이 루트 노드일 때 각 노드들의 부모를 출력해야 한다.

처음엔 NxN크기의 배열로 트리를 저장하고 문제를 풀려고 했으나 N 최댓값이 100000이라 포기했다. 2차원 배열 대신 2차원 벡터를 사용하여 트리를 저장했다. 그리고 DFS로 방문한 적 없는 노드에 방문하여 자신을 호출한 함수의 me 파라미터를 부모로 저장해두고 다시 DFS를 호출한다. 이 과정을 거치면 모든 노드들의 1이 기준일 때의 노드를 올바르게 저장할 수 있다.

다른 답을 찾아보다가 벡터에 대해 무지했다는걸 깨달았다. 난 단순히 벡터를 크기 조절이 자유로운 배열 정도로만 생각하고 있었다.

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

vector<int> v[100];

int main(void) 
{
	v[5].push_back(10);
	v[5].push_back(12);
	
	
	cout << v[5][0]; // 10 출력
	
	return 0;
}

  위의 코드처럼 int형 1차원 벡터를 선언하고 v[5]에 값을 두 개 추가하자 2차원 배열처럼 한 인덱스에 두 값을 저장할 수 있었다. 즉 벡터는 한 번만 선언해도 한 index에 한 가지 값만 넣을 수 있는게 아니라 내가 2차원 배열로 구현하려고 했던 기능처럼 여러 수를 한 행에 넣는 것이 가능하다. 이때까지 C++로 알고리즘 문제를 풀면서 이것도 몰랐다는게 충격적이다. 이제 알았으니 vector를 더 유용하게 사용할 수 있을 것 같다.