[C++] 배열을 통한 인접리스트 표현

오늘은 교육도중에 다른 사람의 코드를 참고하며, 배열을 통해 인접리스트를 표현한 내용이 있어 이를 정리하고자 한다.

기존에 인접리스트를 표현하기 위해서는 스택이나 큐, 덱을 통해 컨테이너를 생성하고 해당 컨테이너에 push해서 구현했다.

struct Stack{...}
node[100];

...

for(int i = 0; i < n ; ++i{
	int a, b;
    node[a].push(b);
}

이런식으로 표현 해 왔다.
만약 인접리스트 때문에 구현해야 하는 상황이라면, stack를 구현하면서 동적할당 대신 최대크기로 배열을 선언하고, pop없이 push(), clear(), operator[]정도만 구현해서 최대한 쉽게 표현했었는데, 이번에 참신하게 인접리스트를 구현하여 적어봤다.

바로

int node[101][101]

for(int i = 0 ; i < n ; ++i){
	int a, b;
    std::cin >> a >> b;
    node[a][++node[a][0]] = b;
}

로 표현 한 것이다.
간단하다. [0]위치에 size를 표현해주고, push할때 들어가야 하는 index는 size + 1이기에 ++node[a][0]으로 표현하여 size와 위치까지 정확하게 넣어 준 것이다. 또한 이후 clear을 위해서 [0]자리만 0으로 초기화 해주면 되니
기존에 stack을 구현 할 필요없이 인접리스트의 기능을 다하고 있는 것이다.

기존

struct Stack {
	int data[201];
	int size;

	void clear() { size = 0; }
	void push(int value) { data[size++] = value; }
	int pop() { return data[--size]; }
	int operator[](int index) { return data[index]; }
};

개선

//size
node[0]

//clear
node[0] = 0;

//push
node[++node[0]] = value;

//pop
node[node[0]--]

되게 간단하면서도, 왜 이런 생각을 못했는지 생각이 들었고, 이후 코드를 작성하면서 많이 활용해볼 방식이라 생각되어 정리해 뒀다.이제 동적할당 아니면 스택 구현 안할거 같은데?