추상적 자료형(Abstract data type)과 자료구조(Data structure)는 엄밀히 말하면 다르다.
가령 스택의 경우는 추상적 자료형이다. 그 이유는 리스트(List)는 정의만 존재하고 구현은 사용자 마음이다.
그러나 만약 누군가가 연결리스트(Linked List), 혹은 배열리스트(Array List, Vector)를 말한다면 그건 자료구조인 셈이다.
그러나 이런 구분이 애매한 녀석들도 존재하기는 한다.
스택(Stack)같은 녀석이 그 정체인데 스택은 추상적 자료형으로 분류되는게 맞으나 사실상 자료구조라고도 볼 수 있다.
왜냐하면 스택을 구현하는 방식이 배열과 연결리스트 두가지가 존재하긴 하지만 사실상 무조건 배열을 쓰는게 이득이기 때문이다.
그래서 필자의 포스팅에서는 추상적 자료형과 자료구조를 엄밀히 구분하지 않고 모두 자료구조라 논하겠다.
참고:
이 사이트의 예제 문제는 백준 사이트(https://www.acmicpc.net/)를 참조합니다.
그래프는 자료구조중에서 실생활에 바로 쓰일 수 있는 강력한 자료구조이다.
현실생활에 밀접한 연관이 있으며 자주 사용하는 예도 볼 수 있다.
일단 정의는 여러개의 노드와 그 노드를 잇는 간선, 그리고 그 간선의 가중치로 이루어진 자료구조를 그래프라고 한다.
근데 이렇게 말하면 딱딱하니 예를 보도록 하자.
세계 지도를 보자.
위의 경우 편의를 위해서 6개의 나라에 동그라미를 쳤다.
위의 동그라미 친 나라들은 바로 노드인 것이다.
보통은 버텍스라고 부르며 알파벳은 V를 사용한다.
이들은 각각의 지점이다.
그럼 이들을 이어보자.
그 중에서 이렇게 이어지게 할 수 있다.
위와 같이 각각의 노드를 연결한 선을 간선이라고 한다.
보통은 엣지(에지)라고 부르며 알파벳은 E를 사용한다.
그래프의 에서 간선이 없다면 연결되지 않은 것으로 간주한다.
이렇게 가중치가 존재할 수 있다.
가령 영국에서 프랑스까지 가는데 통행료가 8만원이라는 식으로 사용할 수 있는 것이다.
물론 통행료가 아니라 길이, 시간 등등 원하는 요소를 사용하면된다.
이런 가중치를 알파벳으로는 W로 나타내는 경향이 있다.
이렇게 일반적으로는 그래프는 각각의 버텍스(노드)들이 연결(엣지)되어있는 형태를 보여주며
일부는 가중치가 있는 경우도 있다.
그래프의 종류는 여러가지가 존재하는데 그 종류는 아래와 같다.
1.무방향 그래프
방향성이 없는 그래프를 의미한다. 무방향은 양방향이라고 봐도 무방하다.
가중치의 존재 여부와는 상관이 없다.
2.가중치 그래프
가중치가 존재하는 그래프를 의미한다.
방향성의 여부와는 상관없다.
3.방향 그래프
방향이 존재하는 그래프를 의미한다.
위의 그래프의 경우 영국에서 프랑스로 갈 수는 있지만 프랑스에서 영국으로 갈수는 없다.
또한 폴란드와 이탈리아의 경우 서로 갈수있지만 서로의 가중치가 다르다.
그리고 영국의 경우 자기자신을 갈 수 있다.
일반적으로는 아무 조건이 없다면 자기자신이 자기자신으로 바로 갈수 없다고 가정한다.
방향그래프 역시 가중치의 유무와는 상관없이 방향이 존재한다면 방향 그래프가 된다.
그래프의 구현하는 방식은 두가지가 있다.
그 중에서 인접행렬을 통해서 그래프를 그리는 예시를 보도록 하자.
무방향 그래프인 이 그래프를 바탕으로 인접행렬 그래프를 만들어 보도록하자.
영국(0),프랑스(1),덴마크(2),독일(3),이탈리아(4),폴란드(5)로 가정한다.
인접행렬로 그래프를 표현한다는 것은 서로의 관계를 행렬로 나타내는 것이다.
일반적으로 보통의 경우 서로의 관계를 행렬로 나타낼 때 int형으로 제작하며 서로 연결 되있음을 1로 나타내게 된다.
bool형으로 제작해서 true로 하는 방법도 있지만 보통은 그렇게 만들지는 않는다. 물론 그래도 상관은 없다.
6 5
0 1
1 2
2 3
1 3
4 5
입력의 첫번째 줄의 앞의 숫자 N은 정점의 갯수, 뒤의 숫자 V는 간선의 갯수이다.
즉 나라가 6개이므로 N은 6개, 각각의 연결은 5개이므로 간선의 갯수 V는 5이다.
아래는 간선의 갯수 만큼 입력을 받는다.
여기서 각각의 캐이스의 의미는 앞이 뒤와 연결되 있다는 것이다.
즉 0 1 이라는 것은 영국(0)과 프랑스(1)가 연결되어 있다는 뜻이다.
#include <stdio.h>
#define MAXSIZE 1000
int N, V;
int arr[MAXSIZE][MAXSIZE];
int main() {
int tx, ty;
scanf("%d %d", &N, &V);
for (int v = 0; v < V; v++) {
scanf("%d %d", &tx, &ty);
arr[tx][ty] = 1;
arr[ty][tx] = 1;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}
위의 코드는 C로짠 인접 행렬 코드이다.
코드의 내용은 전혀 어렵지 않다.
먼저 사용자로 부터 첫째 줄에 입력을 받는다.
중요한것은 for문이다.
값을 받을때 tx와 ty를 각각 받는다.
그리고 그 관계를 배열에 저장하는데 중요한것은 교차해서도 연결해야한다.
이는 무방향 그래프의 특징인데 무방향 그래프는 양방향 그래프이기에 양쪽다 관계가 있음을 보여주어야한다.
즉 0에서 1로가는 것이면서 1에서 0으로 가는 것이다.
영국에서 프랑스로 가는 것이며, 프랑스에서 영국으로 가는 것이다.
아래의 2중 for문은 우리가 제대로 입력했는지 확인하는 용도이다.
0 1 0 0 0 0
1 0 1 1 0 0
0 1 0 1 0 0
0 1 1 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0
과연 연결이 제대로 되어있는지 확인해보자.
영국(0),프랑스(1),덴마크(2),독일(3),이탈리아(4),폴란드(5)순으로 되어 있다.
이를 응용해서 양방향 그래프, 가중치 그래프 역시 쉽게 구현할 수 있다.
이의 구현은 여러분이 해보길 바란다.
그래프를 인접 리스트로 작성해보자.
인접 리스트라고 링크드 리스트로 만든다고 생각하기 쉬운데 물론 그리 만들어도 되지만 보통 배열로 만든다.
즉 리스트 이지만 링크드 리스트가 아닌 array list로 만드는게 좋다.
그 이유는 보통 인접 리스트를 수정하는 경우가 많지 않기 떄문이다.
무방향 그래프인 이 그래프를 바탕으로 인접행렬 그래프를 만들어 보도록하자.
영국(0),프랑스(1),덴마크(2),독일(3),이탈리아(4),폴란드(5)로 가정한다.
6 5
0 1
1 2
2 3
1 3
4 5
입력의 첫번째 줄의 앞의 숫자 N은 정점의 갯수, 뒤의 숫자 V는 간선의 갯수이다.
즉 나라가 6개이므로 N은 6개, 각각의 연결은 5개이므로 간선의 갯수 V는 5이다.
아래는 간선의 갯수 만큼 입력을 받는다.
여기서 각각의 캐이스의 의미는 앞이 뒤와 연결되 있다는 것이다.
즉 0 1 이라는 것은 영국(0)과 프랑스(1)가 연결되어 있다는 뜻이다.
여기서 구현시에 인접리스트로 구할때는 각각의 크기를 저장하는 배열이 필요하다.
int size[MAXSIZE];
이제 코드를 보자.
#include <stdio.h>
#define MAXSIZE 1000
int N, V;
int arr[MAXSIZE][MAXSIZE];
int size[MAXSIZE];
int main() {
int tx, ty;
scanf("%d %d", &N, &V);
for (int v = 0; v < V; v++) {
scanf("%d %d", &tx, &ty);
arr[tx][size[tx]++] = ty;
arr[ty][size[ty]++] = tx;
}
for (int i = 0; i < N; i++) {
printf("%d : ", i);
for (int j = 0; j < size[i]; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}
위의 코드는 인접리스트로 되어있다.
보기에는 크게 바뀐거 없는거 같지만 크기를 저장하는 size배열을 가지고 있다.
물론 C가 아니라 다른 언어의 컨테이너를 쓴다면 크기를 가지고 있을 필요는 없다.
결과를 보자.
0 : 1
1 : 0 2 3
2 : 1 3
3 : 2 1
4 : 5
5 : 4
0번 노드는 1번과 연결되어 있다
1번 노드는 0,2,3번과 연결되어 있다.
아래도 그렇고... 이런식으로 사용하는게 인접리스트로 만든 그래프이다.
인접리스트로 구현하는게 맞을지 인접행렬로 맞을지 햇갈려 하시는 분들이 있다.
특히 알고리즘 문제를 푸는 사람들이 그래프를 자료구조로 구현할때 이런 고민을 한다.
결론 부터말하면 상황에 따라 다르다는 것이다.
둘의 차이는 시간복잡도에 있다.
먼저 공간복잡도에 대해서 이야기하자.
특정 그래프의 노드의 수는 V로 V는 고정이다
그런데 간선의 수 E는 V의 수와 는 상관 없이 최소 0개를 가지며 최대 V^2개를 가지게된다.
물론 실제로 V^2까지 가는 경우는 거의 없다.. 실제 문제들을 보면 V*lgV도 넘지 못하는 경우가 많다.
여기서 인접 행렬의 경우 반드시 최악의 경우인 V^2개로 존재하며
인접 리스트의 경우 E개만 딱 적제할 수 있다.
따라서 그래프를 특정노드에서 부터 탐색하는 경우에는 인접 리스트가 무조건 이득이다.
예를 들자면 다익스트라 알고리즘같은 경우이다.
반대로 갱신이나 삽입, 삭제등의 검색이 아닌 쓰는 작업을 한다면 인접리스트는 그 작업을 수행하기가 어려워진다.
또한 인덱스 번호로 접근할 수 없기 때문에 접근성역시 떨어지는것이 사실이다.
그래서 작업이 빈번하다면 인접 행렬을 사용한다.
예를 들면 플로이드-워셜 같은 알고리즘의 경우이다.
만약 여러분이 아무 정보없이 특정 그래프를 만들어야한다면 검색을 초점을 맞추면된다.
검색을 빨리해서 시간복잡도에서 이득을 봐야한다면 인접리스트로, 그게 아니라면 인접행렬로 짜는 것이 좋다.