그래프 이론의 기초
정점과 간선
- 정점(vertex): 노드를 말한다. 그래프 형성의 기본 단위
- Indegree: 들어오는 간선을 해당 정점의 indegree 라고 한다.
- Outdegree: 나가는 간선을 해당 정점의 outdegree 하고 한다.
- 간선(Edge): 정점을 잇는 선을 말한다. 관계, 경로 등이 될 수 있다.
- 방향에 따라 단방향 간선, 양방향 간선이 존재한다.
- 가중치: 정점-정점 사이의 비용
→ 정점과 간선들로 이루어진 집합을 “그래프(Graph)” 라고 한다.
트리
- 트리는 자식 노드와 부모노드로 이루어진 계층적인 구조를 가진다.
- 무방향 그래프의 일종이고 사이클이 없는 자료구조이다.
트리의 특징
- 부모, 자식 계층 구조를 갖는다. 5번 노드는 6번, 7번 노드의 부모 노드이다.
- 이다. (간선 수 = 노드 수 - 1)
- 임의의 두 노드 사이의 경로는 ‘유일무이’ 하다. 즉 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 하나 존재한다.
여러 트리 중 간단하고 많이 사용하는 트리에 대해 알아보자.
- 이진트리
- 이진 탐색 트리
이진트리(Binary Tree)
- 자식 노드가 최대 2개인 노드들로 구성된 트리이다.
- 2개의 자식 노드는 왼쪽 자식과 오른쪽 자식노드로 나눌 수 있다.
- 이진 트리는 자료의 삽입과 삭제 방법에 따라 나뉜다.
정 이진 트리(Full Binary Tree)
- 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
완전 이진 트리(Complete Binary Tree)
- 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 한다.
- 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽부터 채워야 한다.
포화 이진 트리(Perfect Binary Tree)
- 모든 노드가 꽉 차 있다. 따라서 모든 리프노드의 레벨이 동일하다.
- 정 이진 트리이면서 완전 이진 트리인 경우이다.
이진탐색트리(Binary Search Tree)
이진 트리의 일종으로 다음의 특징을 갖고 있다.
- 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.
- 따라서 “검색”을 하기에 용이하다.
이진탐색트리의 시간 복잡도는?
이진 탐색 트리가 균형잡힌 분포를 가지고 있다면 탐색, 삽입, 삭제, 수정 모두 이다.
하지만 균형이 잡히지 않은 트리는 탐색할 때 시간이 더 걸리는 경우도 있다.
이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰릴 수 있다. → 선형적인 자료구조가 되어버림.
따라서 삽입 순서에 상관없이 트리의 노드들을 회전시키는 등의 방법을 통해서 “균형잡히게 만든 이진탐색트리”가 있다.
- AVL 트리(자가 균형 이진 탐색 트리)
- 레드블랙 트리
그래프 구현과 탐색
그래프를 표현하는 방법은 인접행렬과 인접리스트가 있다.
인접행렬
- 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미한다.
- 행렬 요소가 0이면 두 정점 사이의 경로가 없음을 의미하고, 1이면 두 정점 사이의 경로가 있음을 의미한다.
예시를 들어보면,
👉 3번 노드에서 5번 노드 사이의 단방향 경로가 있다. 이를 인접행렬로 표현한다면? matrix[3][5] = 1
👉 3번 노드에서 5번 노드 사이의 양방향 경로가 있다. 이를 인접행렬로 표현한다면?
- matrix[3][5] = 1
- matrix[5][3] = 1
👉 정점의 개수가 20개인 그래프가 있다. 이를 인접행렬로 표현하고 메모리를 최소로 쓴다고 했을 때 배열은 어떻게 만들어야 할까?
- matrix[ [] * 20] * 20
또는
# 0으로 초기화된 2차원 배열
rows = 3
cols = 3
arr = [[0 for j in range(cols)] for i in range(rows)]
간선 정보로부터 인접행렬 구현하기 (무향 그래프 == 양방향 그래프)
- 입력 정보는 다음과 같다.
- 노드의 개수(node), 간선의 개수(edge)
node, edge = map(int, input().split())
adj = [[0] for _ in range(node) for _ in range(node)]
for _ in range(edge):
src, dest = map(int, input().split()) # 간선정보를 받기 위해 출발, 도착 노드에 대한 정보를 입력받는다.
adj[src][dest] = 1
adj[dest][src] = 1
인접 리스트
- 그래프에서 정점과 간선의 관계를 나타내는 연결리스트를 의미한다.
- 왼쪽의 그래프를 오른쪽의 연결 리스트로 나타낼 수 있다.
- 파이썬에서 인접 리스트는 각각의 노드에 연결된 노드들을 원소로 갖는 리스트들의 배열을 의미한다.
adj[i] : i 번째 노드에 연결된 노드들을 원소로 갖는 리스트
간선 정보로부터 인접리스트 구현하기(무향 그래프)
- 입력 정보는 다음과 같다.
- 노드의 개수(node), 간선의 개수(edge)
node, edge = map(int, input().split())
adj = [[] for _ in range(node)]
for _ in range(edge):
src, dest = map(int, input().split())
adj[src].append(dest)
adj[dest].append(src)
인접행렬 VS 인접리스트
공간복잡도
- 인접행렬: 이다.
- 인접리스트: 이다.
시간복잡도
[간선 1개 찾기]
- 인접행렬: → 행렬의 요소가 1인지 0인지 여부만 조사하면 된다.
- 인접리스트: → adj[i] 리스트를 순회하면서 j 원소가 존재하는지 확인해야 한다.
[모든 간선 찾기]
- 인접행렬: → 2차원 행렬을 탐색하는데 걸리는 비용
- 인접리스트: → 모든 adj[i]를 순회하면서 연결되어 있는 j 원소를 찾으면 된다.
그래프가 희소할 때는 인접리스트, 조밀할 때는 인접행렬!
그래프가 희소할 때는 인접행렬이 인접 리스트보다 메모리를 더 많이 써야 한다.
간선이 없기 때문에 행렬의 대부분이 0이기 때문에 필요없는 공간이 생겨버리기 때문이다.
그래프가 조밀할 때는 인접행렬이 인접 리스트보다 좋다. 어차피 다 연결되어 있기 때문에 메모리 효율성은 동일하고,
인접행렬이 정점과 정점사이 간선이 존재하는지 확인할 때 비용이 들기 때문에 속도가 더 빠르다.
👉 sparce 그래프라면 인접리스트가 좋지만, 코딩테스트 문제에서 인접행렬로 주어진다면 인접행렬로 푸는것이 좋다~
맵과 방향벡터
코딩테스트 문제에서는 그래프를 인접행렬 또는 인접 리스트로 주어지는 경우도 있지만 맵으로 주는 경우도 있다.
👉 맵이 뭘까?
다음 N*N(N=3) 크기의 배열로 표현되는 맵이 주어질 때가 있다.
이런 경우에는 주어진 맵을 입력으로 받고 맵을 기준으로 탐색을 해야한다.
주의할점은 이 맵은 절대 인접행렬이 아니란는 것이다!
코딩테스트 문제에서 맵으로 표현된 그래프!
- 이 맵을 기준으로 4가지 (상,하,좌,우)로 탐색하라는 문제가 많이 등장한다.
- 위 그래프를 (0,0) 에서 탐색을 시작하고 1은 갈 수 있는 지역, 0은 갈 수 없는 지역일 때, 이 맵은 다음의 그래프로도 볼 수 있다.
- 이런 비슷한 문제가 많이 등장하니 풀이 기본틀을 잘 알아두자!
상하좌우(4방향) 탐색과 방향 벡터
그래프를 방향대로 탐색하기 위해서는 2가지가 필요하다.
- 방향 벡터 정의하기
- 현재 위치에서 이동한 방향이 그래프 범위 내에 있는지 확인하기
방향 벡터 정의하기
방향 벡터를 미리 정의해놓고 현재 위치로부터 계산하면 편한다.
dx = [상, 하, 좌, 우]
dy = [상, 하, 좌, 우]
# 이걸 숫자로 표현하면 된다.
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
이 방향 벡터를 현재 원소의 위치에 계산해주면 된다.
for d in range(4):
new_i = i + dx[d]
new_j = j + dy[d]
#new_i, new_j : 이동한 새로운 위치
이동한 방향 범위 확인하기
그래프는 항상 조건이 존재한다. (0,0) ~ (N, N) 안에 위치해있어야 한다.
따라서 이동한 새로운 위치가 그래프 안에, 즉 맵 안에 위치하는지 파악해줘야 한다.
그렇지 않으며 인덱싱 에러를 만날 수 있다.
if (new_i >= 0 and new_i < N) and (new_j >= 0 and new_j < N):
# 어쩌고 저쩌고
참조
Uploaded by N2T
