C++에서 n차원 vector 다루기

n차원 vector 선언

vector<...vector<타입>> 변수명

vector<vector<int>> v1;                         // 2차원 vector 인 v1

vector<vector<vector<bool>>> v2;     // 3차원 vector 인 v2   

 

{행}을 고정하고 {열} 사용자가 앞으로 입력하게 되는 값의 갯수 만큼만 2차원 배열을 생성합니다.

vector<int> v3[5];

 

n차원 vector 초기화

vector의 행과 열의 크기를 아는 경우 다음과 같이 vector 크기를 초기화 할 수 있습니다.

vector<vector<int>> n(n, vector<int>(m));        // n * m 만큼 2차원 vector 공간만 확보
vector<vector<int>> n(n, vector<int>(m, 0));    // n * m 만큼 2차원 vector 0으로 값 초기화

// n * m * k 3차원 vector 공간만 확보
vector<vector<vector<bool>>> t(n+1, vector<vector<bool>>(m+1, vector<bool>(k+1)));
t[1][1][0] = false;

 

사용 예제

1차원 vector 인 tmp에 값을 저장한 후 2차원 vector인 v에 저장하는 방식입니다.

vector<vector<int>> v;
vector<int> tmp;
tmp.push_back(1);
tmp.push_back(2);
v.push_back(tmp);

// at 함수를 통해 2차원 배열의 첫번째 원소에 접근
cout<<v.at(0).at(0); 
 // 배열과 같이 인덱스로 접근도 가능
cout<<v[0][1];

 

행 5개를 위한 메모리를 미리 확보한 후 선언된 인덱스에 저장하는 방식입니다. 

vector<int> v2[5];
v2[0].push_back(1);
v2[0].push_back(2);
cout << '\n';
for(int i=0 ; i< v2[0].size() ; i++){
    cout << v2[0][i] << " ";
}

 

n * m 만큼의 2차원 vector 공간에 값을 저장하는 방식입니다.

vector<vector<int>> v(n, vector<int>(m));
for(int i=0 ; i<n ; i++){
    for(int j=0 ; j<m ; j++){
        v[i][j] = cnt++;
    }
}
for(int i=0 ; i<n ; i++){
    for(int j=0 ; j<m ; j++){
        cout << v[i][j] << " ";
    }
    cout << '\n';
}

 

문제 풀이

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

 

위 문제는 0번 노드부터 N-1번 노드까지 "각 노드의 부모 노드"가 입력 값으로 주어집니다.
만약 -1 0 0 1 1 입력 값이 주어진다면 0번, 1번 노드에 2개의 자식 노드가 연결된 것입니다.
이러한 이해를 바탕으로 지울 노드를 제외한 리프 노드 즉, 자식 노드가 없는 노드가 몇 개인지 구합니다.

1. 2차원 vector를 부모 노드와 자식 노드를 연결되게 저장합니다.
2. DFS를 통해 루트 노드부터 완전 탐색을 시작합니다. 지울 노드는 탐색하지 않습니다.
3. 자식 노드가 없는 노드가 나오면 탐색을 멈추고 1을 반환합니다.
4. 루트 노드가 삭제 노드인 경우 예외 처리를 추가합니다.

 

2차원 vector로 트리 구조를 구현할 수 있습니다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
int n, m, d, root;
vector<int> v[54];
int dfs(int r){
    int leaf = 0;
    int child = 0;
    // 부모 노드 인덱스에 저장된 자식 노드 순회
    for(int i : v[r]){
        // 지울 노드인 경우 탐색 X
        if (i == d) continue;
        // 재귀를 통해 리턴 받은 리프 노드 수확(?)
        leaf += dfs(i);
        child++;
    }
    // 리프 노드인 경우 1 반환
    if(child == 0) return 1;
    return leaf;
}

int main(){     
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i=0 ; i<n ; i++){
        // m 은 각 노드의 부모를 의미!
        cin >> m;
        // -1 일 경우 루트 노드
        // 부모 노드 배열에 해당 자식 노드의 인덱스 저장
        if(m == -1) root = i;
        else v[m].push_back(i);
    }
    cin >> d;
    // 루트 노드가 삭제 노드인 경우 예외 처리
    if(d == root){
        cout << 0 << '\n';
        return 0;
    }
    cout << dfs(root) << '\n';
    return 0;
}

 

참조 : https://astrid-dm.tistory.com/97

2차원 vector, 그리고 3차원 Vector

참조 : https://velog.io/@jt26/STL-Vector-1

[STL] 2차원 Vector