[C++] 이차원 벡터

※  책『Do it! 알고리즘 코딩테스트 (C++편 ) 』에 기반한 글입니다.

 

코딩 테스트 문제에서 그래프와 관련된 알고리즘이 자주 등장하는데, 이때 그래프 구조를 표현하는 데 많이 사용하는 것이 이차원 벡터이다.

우선 2차원 벡터의 선언 및 사용법은 아래 블로그에서..

https://leeeegun.tistory.com/3

[C++ STL] 2차원 vector 선언 및 사용법

---

이차원 벡터를 이용한 그래프 구현

01단계. 이차원 벡터 선언과 초기화

먼저 그래프의 edge를 표현하는 클래스를 만든다.

struct Edge {
	int endNode;
	int value;
};

 

해당 클래스를 자료형으로 하는 이차원 벡터를 초기화 하는 방법을 확인해 보겠다.

vector<vector<Edge>> A;

이차원 벡터의 배열을 선언한 코드이다. 이렇게 선언하면 아직 초기화가 안된 것이다.

노드의 개수가 주어지면 그 개수만큼 벡터 공간을 만들어야 한다.

int N, E;
cin >> N >> E;
A.resize(N + 1);

N이 노드의 개수이다.

A[0]부터 A[N]까지 총 N+1 개의 vector<Edge> 공간을 만들겠다는 의미이다.

이제 초기화를 완료하였다. 생성한 이차원 벡터에 그래프 데이터를 저장해본다.

 

02단계. 그래프 데이터 저장하기

다음과 같은 그래프가 있다.

그래프의 입력값은 다음과 같다.

3 4 // 노드가 3개, 에지가 4개인 그래프
1 2 4 // 1번 노드에서 2번 노드로 가는 가중치 4의 에지가 있음
2 1 10
1 3 7
3 2 6

 

이러한 그래프 데이터를 이차원 벡터 자료구조를 이용하여 저장한다.

for (int i = 0; i < E; i++) {
	int s, e, v = 0;
	cin >> s >> e >> v;
	A[s].push_back({ e, v });
}

저장할 에지의 개수만큼 반복하고, 이차원 벡터에 그래프 데이터를 저장한다.

이렇게 저장하면 실제 이차원 벡터에는 데이터가 다음과 같이 저장된다.

 

03단계. 그래프 데이터 가져오기

이제 그래프 데이터 저장까지 완료하였다. 마지막으로 필요한 데이터를 가져오는 코드를 살펴보겠다.

다음은 1번 노드에서 시작되는 에지 데이터를 가져오는 코드이다.

for (Edge edge : A[1]) {
	int next = edge.endNode;
	int value = edge.value;
	cout << "도착노드: " << next << ", 가중치: " << value << "\n";
}

이 코드를 사용하면 예제 그래프에서 다음과 같은 2개의 에지 데이터를 가져올 수 있다.

이렇게 이차원 벡터를 사용하여 그래프 구조를 표현하는 방법을 익혔다.