Graph
What is graph?
- 그래프는 (Node, Edge)의 튜플로 표현되며 이때 Node를 Vertex라고도 함
- Node: 노드
- Edge: 연결
- Undirected graph: 노드들끼리 방향성이 존재하지 않는 그래프
- Directed graph: Edge끼리의 방향성이 존재하는 graph
- Tree: Graph의 특이 케이스 중 하나
.svg/220px-Tree_(computer_science).svg.png)
Terminology
- Adjacent node: edge로 연결된 이웃 노드
- Path: node A에서 node B로 갈 때 지나가는 node들의 집합 (순서를 가짐)
- Complete graph: 어떤 node 쌍을 골라도 edge가 존재하는 graph
- undirected일 경우 연결만 존재하면 됨
- nC2개의 edge 존재 n * (n-1) / 2
- Directed일 경우 양방향으로 존재
- nP2개의 edge 존재 n * (n-1)
- undirected일 경우 연결만 존재하면 됨
- Weighted graph: edge마다 weight 존재해서 중요도를 다르게 부여한 graph
Implementation: Adjacency Matrix
- 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- undirected graph에만 사용 가능
- Vertices: Vertex에 해당하는 index를 알려 주는 1차원 배열
- Adjacency Matrix: Vertex끼리의 edge 존재 유무와 weight를 알려 주는 2차원 배열
- Array Based이기 때문에 충분한 크기를 설정해 둬야 함
- Vertices의 index를 정렬해 놓으면 Searching 시간을 줄일 수 있음
- Sorted인 경우 이진 탐색 O(logN), Unsorted인 경우 완전 탐색 O(N)
- edges[0][5]=800: vertices[0]인 Atlanta와 vertices[5]인 Houston 사이를 이어 주는 800이라는 weight를 가진 path 존재
- python 구현
A / \ B---C | A | B | C | ---|---|---|---| A | 0 | 1 | 1 | ---|---|---|---| B | 1 | 0 | 1 | ---|---|---|---| C | 1 | 1 | 0 | ---|---|---|---|INF = 999999999 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ]from QueType import * from StackType import * NULL_EDGE = 0 def index_is(vertices, vertex): index = 0 while index < len(vertices) and vertex != vertices[index]: index += 1 if not index < len(vertices): return -1 else: return index class GraphType: def __init__(self, maxV=50): self.numVertices = 0 self.maxVertices = maxV self.vertices = [None] * maxV self.edges = [[NULL_EDGE] * maxV for _ in range(maxV)] self.marks = [None] * maxV def add_vertex(self, vertex): self.vertices[self.numVertices] = vertex for index in range(self.numVertices): self.edges[self.numVertices][index] = NULL_EDGE self.edges[index][self.numVertices] = NULL_EDGE self.numVertices += 1 def add_edge(self, fromVertex, toVertex, weight): row = index_is(self.vertices, fromVertex) col = index_is(self.vertices, toVertex) self.edges[row][col] = weight def weight_is(self, fromVertex, toVertex): row = index_is(self.vertices, fromVertex) col = index_is(self.vertices, toVertex) return self.edges[row][col] def get_to_vertices(self, vertex, adjVertices): fromIndex = index_is(self.vertices, vertex) for toIndex in range(self.numVertices): if(self.edges[fromIndex][toIndex] != NULL_EDGE): adjVertices.enqueue(self.vertices[toIndex]) def clear_marks(self): for index in range(self.numVertices): self.marks[index] = False def is_marked(self, vertex): index = index_is(self.vertices, vertex) return self.marks[index] def mark_vertex(self, vertex): index = index_is(self.vertices, vertex) self.marks[index] = True def delete_edge(self, fromVertex, toVertex): row = index_is(self.vertices, fromVertex) col = index_is(self.vertices, toVertex) self.edges[row][col] = NULL_EDGE
Implementation: Adjacency List
- 리스트로 그래프의 연결 관계를 표현하는 방식
- undirected graph, directed graph 모두 적용 가능
- Vertices: Vertex에 해당하는 index를 알려 주는 1차원 배열
- Vertex list: Vertex 마다 edge로 연결된 다른 노드들을 Linked list로 표현
- 해당 노드에서 뻗어나가는 edge만
- adjacent node의 연결
- edges[0][5]=800: vertices[0]인 Atlanta에서 vertices[5]인 Houston까지 가는 데 800이라는 weight를 가진 path 존재
- python 구현
A / \ B---C A -> [B, C] B -> [A, C] C -> [A, B]graph = [[] for _ in range(3)] graph[0].append((1, 7)) graph[0].append((2, 5)) graph[1].append((0, 7)) graph[2].append((0, 5))
Matrix VS List
- matrix
- graph의 크기가 작은 경우에는 유용
- 그래프의 크기가 매우 크면 연결이 없는 부분에 대한 matrix의 메모리 낭비가 발생할 수 있음
- list
- 인접한 노드를 찾기 위해서는 각 노드의 인접 리스트를 순회해야 하기에 search 과정이 오래 걸릴 수 있음
- 노드와 노드 사이 연결 여부를 확인할 때에도 리스트를 순회해야 해서 시간이 소요됨
Union
- 서로소 집합 (Disjoint Sets): 공통 원소가 없는 두 집합
- 서로소 집합 자료 구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료 구조
- 트리 자료 구조를 활용하여 서로소 집합 구현
- 단계
- union 합집합 연산을 확인하여 서로 연결된 두 노드 a, b를 확인
- a, b의 루트 노드인 a’, b’를 각각 찾음
- 모든 union 연산을 처리할 때까지 1번 과정 반복
- union 합집합 연산을 확인하여 서로 연결된 두 노드 a, b를 확인
- 예시
- 아래 연산은 1, 4와 2, 3과 2, 4와 5, 6이 같은 집합이라는 뜻
- 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 설정해서 연결 표시
- 이 과정을 반복하다가 4번 노드의 루트는 1번 노드이기 때문에 2번 노드도 1번 노드를 가리키도록 한다
- 아래 연산은 1, 4와 2, 3과 2, 4와 5, 6이 같은 집합이라는 뜻
- 서로소 집합의 자료 구조는 연결성을 통해 확인할 수 있음
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호
if parent[x] != x:
return find_parent(parent, parent[x])
return x
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
# 더 작은 노드의 부모 노드 변경하기
if a < b:
parent[b] = a
else:
parent[a] = b- 경로 압축 기법
-
위의 방법은 만약 노드가 일렬로 연결되어 있으면 부모의 부모의 부모 노드를 타고 가는 방식으로 비효율적
-
경로 압축 기법을 통해 모든 노드의 부모 자리에 가장 최상위 부모를 두는 방식 채택 가능
[https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F6pADO%2Fbtrb6TQ7hCI%2F3j8KnlaAzGaIXSK1xopTyk%2Fimg.png](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F6pADO%2Fbtrb6TQ7hCI%2F3j8KnlaAzGaIXSK1xopTyk%2Fimg.png)# 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x]
-
Cycle
- 서로소 집합을 통해 무방향 그래프 내에서의 사이클 판별이 가능
- 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복해 사이클 확인
- 단계
- 각 간선을 확인하며 두 노드의 루트 노드 확인
- 루트 노드가 서로 다르다면 두 노드에 대해 union 연산 수행
- 루트 노드가 서로 같다면 사이클 발생
- 그래프에 포함되어 있는 모든 간선에 대해 1번 과정 반복
- 각 간선을 확인하며 두 노드의 루트 노드 확인
- 예시
- 모든 노드에 대해 자기 자신을 부모로 설정하는 형태로 부모 테이블 초기화
- 간선 (1, 2)를 확인하고 루트 노드를 업데이트
- 간선 (1, 3)을 확인하고 루트 노드를 업데이트
- 간선 (2, 3)을 확인할 때 이미 루트 노드가 동일하다면 사이클 발생
- 모든 노드에 대해 자기 자신을 부모로 설정하는 형태로 부모 테이블 초기화
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
# 더 작은 노드의 부모 노드 변경하기
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# 사이클 발생 유무
cycle = False
for i in range(e):
a, b = map(int, input().split())
# 사이클이 발생한 경우 종료
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
# 사이클이 아니라면 합집합 실행
else:
union_parent(parent, a, b)Algorithm
Kruskal Algorithm
- 모든 노드를 연결하는 문제에 자주 사용
- 그리디 알고리즘으로 분류됨
- 신장 트리를 찾는 알고리즘
- 신장 트리: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
- 최소 신장 트리 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘
- 단계
- 간선 데이터를 비용에 따라 오름차순으로 정렬
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
- 사이클이 발생하는 경우 최소 신장 트리에 포함하지 않음
- 다음 그래프의 최소 신장 트리 구하기
- 간선 데이터를 비용에 따라 오름차순으로 정렬
- 가장 짧은 간선을 선택 → (3, 4) 선택되고 이것을 집함에 포함 
- 처리하지 않은 간선 중 가장 짧은 (4, 7) 선택 
- 처리하지 않은 간선 중 가장 짧은 (4, 6) 선택 
- 처리하지 않은 간선 중 가장 짧은 (6, 7) 선택 
- 이 과정을 반복해서 최소 신장 트리를 구하고 이 간선의 비용을 다 더하기 
- 간선 데이터를 비용에 따라 오름차순으로 정렬
def find_parent(parent, x):
# 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
# 더 작은 노드의 부모 노드 변경하기
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
# 간선 정보 입력받기
for i in range(e):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
# 간선을 비용 순서로 정렬
edges.sort()
# 간선을 하나씩 확인
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않을 때만 집합에 포함
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost- 크루스칼 알고리즘의 시간 복잡도는 O(E logE) 시간 복잡돠를 가짐
- 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분은 간선을 정리하는 작업이며, E개의 데이터를 정렬했을 때의 시간 복잡도이기 때문
Topology Sort
- 위상 정렬: 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
- 예를 들어 선수과목을 고려한 학습 순서 결정 같은 문제
- 그래프 상에 선후 관계가 있을 경우
- 진입차수: 특정한 노드로 들어오는 간선의 개수
- 진출차수: 특정한 노드에서 나가는 간선의 개수
- 단계
- 진입차수가 0인 노드를 큐에 넣음
- 큐가 빌 때까지 다음의 과정을 반복
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
- 새롭게 진입 차수가 0이 된 노드 큐에 넣기
- 예시
- 위상 정렬을 수행할 그래프인 사이클이 없는 방향 그래프 준비 
- 진입차수가 0인 모든 노드를 큐에 넣음 → 1이 들어감 
- 노드 1을 꺼낸 뒤에 노드 1에서 나가는 간선 제거하고 새롭게 진입 차수가 0이 된 노드 삽입
- 노드 2 꺼낸 뒤 노드 2에서 나가는 간선 다 제거하고 새롭게 진입 차수가 0이 된 노드 삽입 
- 이 과정을 반복하면 위상 정렬 결과 
- 위상 정렬을 수행할 그래프인 사이클이 없는 방향 그래프 준비 
- 위상 정렬의 시간 복잡도는 O(V + E)
- 위상 정렬을 수행할 때 차례대로 모든 노드를 확인하면서 간선을 차례대로 제거해야 하기 때문
Practice
1로 만들기
- 문제
- 학교에서 학생들에게 0번부터 N번까지의 번호를 부여
- 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1 개의 팀이 존재
- 이때 선생님은 '팀 합치기'연산과 '같은 팀 여부 확인'연산을 사용
- '팀 합치기' 연산은 두 팀을 합치는 연산
- '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산
- 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인'연산에 대한 연산 결과를 출력하는 프로그램을 작성
- 입력 조건
- 첫째 줄에 N, M이 주어짐 M은 입력으로 주어지는 연산의 개수 (1 <= N, M <= 100,000)
- 다음 M개의 줄에는 각각의 연산이 주어짐
- '팀 합치기' 연산은 0 a b 형태로 주어짐 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미
- '같은 팀 여부 확인' 연산은 1 a b 형태로 주어짐 이는 a번 학생과 b번 학생이 같은 팀에 속해 있는지를 확인하는 연산
- a와 b는 N 이하의 양의 정수
- 출력 조건
- '같은 팀 여부 확인'연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
# 더 작은 노드의 부모 노드 변경하기
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선의 개수 입력받기
n, m = map(int, input().split())
parent = [0] * (n + 1)
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, n + 1):
parent[i] = i
for i in range(m):
oper, a, b = map(int, input().split())
# 합집합 연산인 경우
if oper == 0:
union_parent(parent, a, b)
# 찾기 연산인 경우
elif oper == 1:
if find_parent(parent, a) == find_parent(parent, b):
print("Yes")
else:
print("No")
도시 분할 계획
커리큘럼
- 문제
- 동빈이는 온라인으로 컴퓨터 공학 강의를 듣고 있음
- 이 때 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있음
- 동빈이는 총 N개의 강의를 듣고자 함
- 강의는 1번부터 N번까지의 번호를 가짐
- 또한 동시에 여러 개의 강의를 들을 수 있다고 가정
- 예를 들어, N = 3일 때, 3번 강의의 선수 강의로 1번과 2번 강의가 있고, 1번과 2번 강의는 선수 강의가 없다고 가정
- 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 가정
- 1번 강의: 30시간
2번 강의: 20시간
3번 강의: 40시간 - 이 경우, 1번 강의를 수강하기까지의 최소 시간은 30시간, 2번 강의를 수강하기까지는 최소 20시간, 3번 강의를 수강하기까지는 최소 70시간이 필요
- 동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지는 걸리는 최소 시간을 출력하는 프로그램을 작성
- 입력 조건
- 첫째줄에 동빈이가 듣고자 하는 강의의 수 N(1 <= N <= 500)이 주어짐
- 다음 N개의 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 강의들의 번호가 자연수로 주어지며, 각 자연수는 공백으로 구분
- 이 때 강의 시간은 100,000 이하의 자연수
- 각 강의 번호는 1부터 N까지로 구성되며, 각 줄은 -1로 끝남
- 출력 조건
- N개의 강의에 대해 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력
from collections import deque
import copy
# 노드의 개수 입력받기
v = int(input())
# 모든 노드에 대한 진입차수 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v + 1)]
# 각 강의 시간을 0으로 초기화
time = [0] * (v + 1)
# 방향 그래프의 모든 간선 정보를 입력받기
for i in range(1, v + 1):
data = list(map(int, input().split()))
time[i] = data[0]
for x in data[1:-1]:
indegree[i] += 1
graph[x].append(i)
# 위상 정렬 함수
def topology_sort():
# 알고리즘 수행 결과를 담을 리스트
result = copy.deepcopy(time)
q = deque()
# 처음 시작할 때 진입차수가 0인 노드 큐에 삽입
for i in range(1, v + 1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
for i in graph[now]:
result[i] = max(result[i], result[now] + time[i])
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
for i in range(1, v + 1):
print(result[i])
topology_sort()
