C++ 2차원 벡터 동적 할당 사용법

그래프 문제를 풀 때 노드의 개수 N의 범위가 매우 크면 벡터의 크기를 함부로 설정하기가 난감하다.

 

vector<int> graph[100000];

 

와 같이 할당하면 N = 10처럼 노드의 개수가 적은 경우에 메모리 낭비가 되고, 그렇다고

 

vector<int> graph[10];

 

처럼 작게 할당해버리면 N의 범위가 큰 경우에는 범위를 초과해버리기 때문이다.

 

따라서 vector의 2차원 동적 할당을 이용해 그래프를 만들어준다.

 

vector<vector<int>> v;

 

2차원 벡터란 위와 같이 벡터 안에 벡터를 또 집어 넣는 것이다.

 

이렇게 하면 v의 행과 열 범위를 동적으로 만들 수 있다.

 

N개의 노드가 있고 M개의 간선이 있는 무방향 그래프가 있다고 해보자.

 

아래는 N과 M을 입력 받아 M개의 간선 정보를 통해 그래프를 그리는 예시이다.

 

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, M, a, b, i, j;
	cin >> N >> M;
	graph.resize(N + 1);
	for (i = 0; i < M; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (i = 1; i <= N; i++) {
		cout << i << "번 노드와 연결된 노드: ";
		for (j = 0; j < graph[i].size(); j++) {
			cout << graph[i][j] << ' ';
		}
		cout << "\n";
	}
}

 

위에서 N을 입력받고 

 

graph.resize(N+1);

 

을 해주었는데, 이렇게 하면 N + 1개의 행을 미리 할당할 수 있다.

 

[결과]

2차원 벡터 동적 할당을 이용한 그래프 예시 결과