[자료구조와 알고리즘] Graphs
9-1. Dictionary and Copy in Python
AL09-3
Python Dictionary
우리가 많이 쓰는 리스트 자료구조는 순서가 있었음.(ordered)
- An unordered collection of items: Each item has a key/value pair (순서가 없다!!)
- Dictionary is mutable and iterable.
- Keys are unique and must be immutable(바뀔 수 없다)
마지막줄 뭥미?? -> 튜플이 원소인 리스트를 dict() 함수에 넣으면 dictionary가 생성됨
>>> print(a)
{'brand': 'Ford', 'model': 'taurus'}
AL09-4
a[‘Key’] vs. a.get(‘Key’)
-
내가 찾으려는 data가 기존의 dictionary에 없는 경우
- key로 접근하는 경우에 오류가 발생한다.
- get함수로 접근하는 경우 오류가 발생하지 않음
- 해당 key값을 dictionary를 새로 추가하려면 key를 통해서 대입시키면 할 수 있음
AL09-5
Python Set
- An unordered collection of items: Each item is a key
- Set is mutable and iterable
- Each item is unique and must be immutable
- set에 리스트는 못 집어 넣는다.(immutable한 item만 가질 수 있음.)
>>> a = {123, "sdf", [1,2,3]}
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>
-
set()함수 안에는 list 혹은 tuple, string을 전달할 수 있다.
-
항상 순차적으로(1,2,3) 나오는 것이 아니다. {3,2,1} 이런식으로도 나올 수 있고, {2,1,3} 이런 식으로도 나올 수 있다. 순서가 중요한 것이 아니라 어떤 item들이 들어있는가가 중요한 것
-
unordered collection이기 때문
AL09-6
- 비어 있는 set을 만드려면 반드시 set()을 사용
- a = {} 는 dictionary를 만드는 것이기 때문.
- update() 함수를 호출할 때는 반드시 iterable object를 넘겨주어야 함.
- list, tuple, set, string, …
- discard vs. remove
- 제거하려는 item이 set에 없는 경우 remove를 사용 시 error가 발생한다.
>>> a = {1, 2, 3, 4, 5}
>>> b = {4, 5, 6, 7, 8}
>>> a | b # == a.union(b) == b.union(a)
>>> a & b # == a.intersection(b) == b.intersection(a)
>>> a - b # == a.difference(b) != b.difference(a)
AL09-7
3 가지 방식의 copy (in python)
Copy: Assignment using ‘=’ operator
- b랑 a는 같은 object를 가리키고 있기 때문에 id도 같다.
- object의 내용을 바꾸면 양쪽이 같이 update 된다.
a[2] = 9를 하면 integer object는 immutable이기 때문에 9라는 integer object가 하나 생겨서 2번 index가 그 object를 가리키게 되고 a라는 리스트는 mutable이기 때문에 계속해서 같은 list object를 가리키고 있을 것이다. 따라서 기존의 리스트에 값을 추가하는 것이기 때문에 id는 그대로 일 것이고 b는 a와 같은 객체를 가리키고 있기 때문에 둘을 찍어보면 둘 다 9가 추가된 결과가 출력 될 것이다.
- 3은 garbage variable.
AL09-8
Copy: shallow copy
- 리스트 object가 copy 되면서 새로운 object가 하나가 별도로 생겨난다.
- 그러나 그 object 안의 딸려 있는 애들까지 copy하지는 않는다.(no recursion)
- 그래서 a와 b가 가리키는 object는 다르기 때문에 id가 다르다.
- 마지막 부분을 보면 b[2][0] = 9는 integer object를 바꾸는 것이 아니라 list의 element를 바꾸는 것이기 때문에 mutable한 객체를 바꾸는 것은 별도의 object를 만들지 않고 따라서 a 내용과 공유 하고 있던 리스트의 내용을 바꾼 것이기 때문에 a를 출력해 보아도 b와 같은 결과가 나오는 것을 볼 수 있다.
- shallow copy를 이용하는 이유는 memory 절약과 operation의 신속함을 위해서 사용하는 것이다.
다음 그림은 new object를 만드는 방식의 copy 모듈을 사용했을 때의 그림이다.
AL09-9
Copy: deep copy
- recursive copy: 내가 copy할 object를 하나도 빠지지 않게 구석구석 하나하나 모든 것을 copy하는 것
- 그말인 즉슨, a와 b가 공유하고 있는 객체가 하나도 없다는 것을 말하고 어떤 한 변수의 내용을 바꿨을 때 다른 변수의 내용은 바뀌지 않는 것을 의미한다.
정리
Shallow copy : 복사대상은 새로운 공간에 할당되지만 대상안에 있는 요소는 원본과 동일 대상을 참조합니다. Deep copy : 복사대상 뿐만 아니라 대상안에 있는 요소들도 새로운 공간에 할당됩니다.
case1: mutable 객체 안에 mutable 객체가 포함된 경우
ori = [1,2]
a = [ori, 3]
b = copy.copy(a)
c = copy.deepcopy(a)
case 2: immutable 객체 안에 mutable 객체가 포함된 경우
ori = [1,2]
a = (ori, 3)
b = copy.copy(a)
c = copy.deepcopy(a)
case 3: immutable 객체 안에 immutable 객체가 포함된 경우
ori = (1,2)
a = (ori, 3)
b = copy.copy(a)
c = copy.deepcopy(a)
case 4: mutable 객체 안에 immutable 객체가 포함된 경우
ori = (1,2)
a = [ori, 3]
b = copy.copy(a)
c = copy.deepcopy(a)
요약
- deep copy target이 mutable 일 경우 - target : 원본과 같은 참조 - target의 포함된 객체 중 mutable 객체는 새로운 사본을 생성 - target의 포함된 객체 중 immutable 객체는 원본과 같은 참조
-
deep copy target이 immutable 일 경우 - target의 포함된 객체 중 mutable 객체가 있으면 target은 새로운 사본을 생성 - target의 포함된 객체 중 mutable객체가 없다면 target은 원본과 같은 참조
- shallow copy target이 mutable 일 경우 - target : 새로운 사본을 생성 - target의 포함된 객체 : 원본과 같은 참조
- shallow copy target이 immutable 일 경우 - target : 원본과 같은 참조 - target의 포함된 객체 : 원본과 같은 참조
- immutable로만 구성된 객체일 경우 - 수정 불가하므로 새로운 공간을 만들지 않는 것으로 예상하며, =(Assignment)와 같게 동작합니다. - deep, shallow copy 동일 함.
- 사용자 class 같은 개념으로 적용됨.
9-2. Graph and its Representations
AL09-11
Graphs
A graph is a set of vertices and edges that form connections between the vertices. In a more formal approach, a graph G is an ordered pair of a set V of vertices and a set E of edges, given as G = (V, E) in formal mathematical notation.
maze를 생각해 봤을 때, 교차 부분을 node로 하고 node끼리 연결한 것을 edge로 하면 이러한 구조를 graph라고 한다.
-
sparse graph: 노드 개수에 비해서 link 갯수가 적은 것
-
dense graph: 노드 개수에 비해서 link 갯수가 많은 것
-
sparse와 dense를 나누는 기준은 없음. 그냥 느낌상으로 생각하는 것
V = n일 때, 연결할 수 있는 최대 link(edge)의 갯수는 n(n-1)/2 개 이다.
- 하나의 노드에서 다른 노드로 연결할 수 있는 link 수는 (n-1)이고 노드가 총 n개 있는데 중복을 1/2를 곱하여 처리하면 n(n-1)/2라는 공식이 나옴.
AL09-12
Definition
- A path in a graph is a sequence of vertices connected by edges.
- 특정 노드에서 노드까지의 path의 갯수는 이론상 무한대이다.(왔던 길을 다시 갈수 있다는 가정)
- A simple path is one with no repeated vertices.
- 한 노드를 두 번 지나지 않는 path.
- A cycle is a path with at least one edge whose first and last vertices are the same.
- 한 노드에서 출발하여 다시 그 노드로 돌아와서 폐곡선을 만드는 path.
- 한 노드를 여러번 지날 수 있기 때문에 이론상 무한의 갯수를 가짐.
- A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices).
- 한 노드를 두 번 지나지 않는 cycle.
- The length of a path or a cycle is its number of edges.
Definition
- A graph is connected if there is a path from every vertex to every other vertex in the graph.
-
A graph that is not connected consists of a set of connected components, which are maximal connected subgraphs.
- degree: 한 노드에서 다른 노드로 갈 수 있는 가지의 수
- 어떤 노드에서 연결된 link의 갯수
AL 09-13
Definition
- A tree is an acyclic connected graph.
- A disjoint set(서로소 집합) of trees is called a forest.
- tree가 모인 구조를 forest라고 한다.
For, example, a graph G with V vertices is a tree if and only if it satisfies any of the following five conditions:
- G has V-1 edges and no cycles.
- G has V-1 edges and is connected.
- G is connected, but removing any edge disconnects it.
- G is acyclic, but adding any edge creates a cycle.
- 어느 두 노드를 연결하면 cycle이 되어 버림.
- Exactly one simple path connects each pair of vertices in G.
위 다섯 문장은 다 같은 말이며, 이 중 하나만 만족해도 graph인 것이다.
AL09-14
Directed graphs
In a directed graph, the edges provide the information on the direction of connection between any two nodes in a graph.
- Undirected graph
- 방향이 없는 graph
- In-degree:
- 해당 노드로 들어오고 있는 link의 갯수
- Out-degree:
- 해당 노드로 나가고 있는 link의 갯수
- (directed) path
- (directed) cycle
AL09-15
Weighted graphs
A weighted graph is a graph that has a numeric weight associated with the edges in the graph. It can be either a directed or an undirected graph. This numerical value can possibly be used to indicate distance or cost, depending upon the purpose of the graph.
- directed 이든 undirected 이든 상관 없다.
In this example, AD and ABCD represent two different paths.
- 노드를 무조건 적게 거친다고 좋은 path라고 볼 수 없는 것이다.
09-16
Graph representations
그래프 정보를 파이썬으로 저장하는 방법(표현)
We can choose between two standard ways to represent a graph G = (V, E):
- as a collection of adjacency lists or as an adjacency matrix.
Either way applies to both directed and undirected graphs.
The adjacency-list representation provides a compact way to represent sparse graphs
-
those for which E is much less than V 2
We may prefer an adjacency-matrix representation, however, when the graph is dense
-
E is close to V 2
or when we need to be able to tell quickly if there is an edge connecting two given vertices.
09-17
Adjacency lists
이웃하고 있는 노드들을 리스트에 저장하여 그래프를 표현하는 방식.
중요한 점은 이웃이라는 wording의 의미가 해당 노드로 들어올 수 있는 노드를 의미하는 것이다. 그래서 undirected라면 상관이 없겠지만 directed graph인 경우 이 점을 유의하여야 한다.
- key: 노드(A, B, C, E, F)
- value: key 노드와 이웃하고 있는 노드들의 리스트
따라서 dictionary 자료형을 이용한다.
graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['E', 'C', 'A']
graph['C'] = ['A', 'B', 'E', 'F']
graph['E'] = ['B', 'C']
graph['F'] = ['C']
{'A': ['B', 'C'], 'B': ['E', 'C', 'A'], 'C': ['A', 'B', 'E', 'F'], 'E': ['B', 'C'], 'F': ['C']}
dictionary를 통해 필요한 만큼만 딱 저장하기 때문에 메모리상으로 효율적이다.
- sparse graph -> link가 적다 -> adjacency (이웃) 이 적다.
09-18
Adjacency lists-cont.
노드의 이름이 숫자로 되어있는 경우 굳이 앞에서처럼 dictionary를 사용할 필요없이 list로 할 수 있다.
graph = list([0])
graph.append([2, 3])
graph.append([1, 3, 4])
graph.append([1, 2, 4, 5])
graph.append([2, 3])
graph.append([3])
# [[0], [2,3], [1,3,4], [1,2,4,5], [2,3], [3]]
- 처음에 0을 넣은 이유는 graph의 노드 이름이 숫자로 되어있는데 1부터 시작하기 때문에 숫자로 접근하기 위해 list로 구현하여 각 index로 접근할 수 있도록 한 것이다.
09-19
Adjacency matrices
dense(빽빽한) graph에서 효율적인 방법 -> matrix
- undirected graph이기 때문에 diagonal 대칭으로 되어있는 것을 볼 수 있다.
- 즉, 연결된 두 노드는 양방향으로 이동가능 하기 때문에 A의 이웃 노드 중 B가 있다고 하면 B의 이웃노드에는 반드시 A 노드가 있다는 것을 알 수 있으며
- 이를 matrix로 표현했을 때 그 matrix는 항상 diagonal symmetry임을 알 수 있다.
[[0, 1, 1, 0, 0],
[1, 0, 0, 1, 0],
[1, 1, 0, 1, 1],
[0, 1, 1, 0, 0],
[0, 0, 1, 0, 0]]
Q) tree에서는 linked list로 했는데 왜 graph는 list를 사용하나요?
A) tree도 필요에 의해 리스트에다가 할 수 있는 것이고 graph도 linked list로 구현할 수 있다. 방법의 차이일 뿐이다.
Graph Algorithms
AL09-21
Graph Traversals
A graph traversal means to visit all the vertices of the graph, while keeping track of which nodes or vertices have already been visited and which ones have not.
- graph traversal: 그래프의 모든 노드를 방문하는 것
- 어느 노드르 방문했는지 기록
A graph traversal algorithm is efficient if it traverses all the nodes of the graph in the minimum possible time.
Graph traversal algorithms are very important in answering many fundamental problems
- they can be useful to determine how to reach from one vertex to another in a graph, and which path from the A to B vertices in the graph is better than the other paths.
In the next section, we will discuss two important graph traversal algorithms:
- breadth-first search(BFS)
- depth-first search(DFS)
- graph는 tree와 다르게 left/right child 개념이 있지 않기 때문에 inorder, postorder, preorder가 없다.
09-22
Breadth-first search(BFS)
bfs는 queue를 사용한다. -> bbq
Breadth-first traversal algorithms work breadth-wise in the graph.
- A queue data structure is used to store the information of vertices that are to be visited in the graph.
We begin with the starting node, the A node. Firstly, we visit that node, and then we look up all of its neighboring, or adjacent, vertices.
위 그래프를 A노드에서 시작하여 BFS로 순회를 하면 다음과 같은 경우의 수들이 나올 수 있다.
- A-E-C-B-D
- A-C-E-B-D
- A-B-C-E-D
근데 만약 시험에 ‘순회한 알파벳 순서를 적으시오’ 와 같은 문제가 나온다면 마지막 경우처럼 적어야 한다.
- 편리를 위해 알파벳 순서대로
discovered: queue에 한 번이라도 들어간 노드를 다시 queue에 넣는 것을 방지하기 위해서 discovered 리스트에 저장을 해 둔다.
visit: 방문한 노드의 순서를 기록 -> 최종 결과
되도록 알파벳 순서로 인근한 노드를 큐에 집어넣도록 한다.
09-23
# the graph in page 208
graph1 = { # 26
'A': ['B', 'G', 'D'],
'B': ['A', 'F', 'E'],
'C': ['F', 'H'],
'D': ['F', 'A'],
'E': ['B', 'G'],
'F': ['B', 'D', 'C'],
'G': ['A', 'E'],
'H': ['C']
}
ans = breadth_first_search(graph1, 'A') # 37
print(*ans, sep='-')
실행 결과
09-24
from collections import deque # 1
def breadth_first_search(graph, root): # 4
#sequence of visited nodes
visited = []
discovered = []
queue = deque([root])
discovered.append(root)
while len(queue) > 0: # 12 ; queue에 뭐라도 있으면 반복
node = queue.popleft()
visited.append(node)
undiscovered = set(graph[node]).difference(set(discovered))
if len(undiscovered) > 0: # 17
for elem in sorted(undiscovered):
queue.append(elem)
discovered.append(elem)
return visited # 22
set(graph[node]).difference(set(discovered)) : 한 노드와 인접한 노드 중에서 discovered 된 것은 제외한 것을 undiscovered에 저장한다.
queue에서 뺀 것이 result 리스트에 들어간다.
graph[node] 는 node의 인접 노드들의 정보가 담겨있기 때문에
09-25
Depth-first search(DFS)
DFS는 머릿속에 stack을 그리고 생각하면 편하다!
As the name suggests, the DFS algorithm traverses the depth of any particular path in the graph before traversing its breadth. As such, child nodes are visited first before sibling nodes. The stack data structure is used to implement the DFS algorithm.
-
DFS도 역시 discovered라는 이미 발견된적이 있는지를 저장하는 리스트가 존재한다.
- 인근한 노드 중에서 발견되지 않는 노드를 stack에 추가해 가면서 탐색을 진행한다.
- A-B-D-C-E
- 스택에서 꺼냈다(pop)는 것은 그 노드를 방문한 것이다.
- 알파벳 순서로 하기 위해서 인근한 노드를 stack에 집어 넣을 때는 아래에 더 높은 위치에 있는 알파벳을 넣어야 한다. 즉, 넣을 때는 역순으로 넣는 것이다.
09-26
# the graph in page 211
graph2 = { # 23
'A': ['B', 'S'],
'B': ['A'],
'S': ['A', 'G', 'C'],
'D': ['C'],
'G': ['S', 'F', 'H'],
'H': ['G', 'E'],
'E': ['C', 'H'], # 30
'F': ['C', 'G'],
'F': ['D', 'S', 'E' ,'F']
}
ans = depth_first_search(graph2, 'A') # 35
print('-'.join(ans))
실행 결과
09-27
def depth_first_search(graph, root): # 1
#sequence of visited nodes
visited = []
# nodes which are discovered & stacked
discovered = []
stack = [root]
discovered.append(root)
while stack: # 9 ; stack이 비지 않았으면 (= len(stack))
node = stack.pop()
visited.append(node)
undiscovered = set(graph[node]).difference(set(discovered))
if undiscovered: # 14
for elem in sorted(undiscovered, reverse=True):
stack.append(elem)
discovered.append(elem)
return visited # 19
발견되지 않은 노드를 스택에 넣고 discovered에도 넣는데 이때 알파벳 순서대로 스택에서 빼고 싶기 때문에 reverse=True이다.
09-28
Example: BFS and DFS (시험 문제)
For any vertex v reachable from s, the simple path in the breadth-first tree from s to v corresponds to a "shortest path" from s to v in G, that is, a path containing the smallest number of edges.
- s로부터 도달가능한 임의의 노드 v에 대해, 너비 우선 트리에서 s에서 v로 가는 단순한 path는 G라는 그래프에서 s to v 로 가는 가장 짧은 path 즉, 가장 적은 숫자의 edges를 포함하는 path이다.
09-29
- 1-2-5-3-6 : BFS
- len() - 1 -> answer
09-30
# 정답 코드
import sys
from collections import deque
def breadth_first_search(graph, root):
visited = []
discovered = []
queue = deque([root])
discovered.append(root)
while len(queue) > 0:
node = queue.popleft()
visited.append(node)
undiscovered = set(graph[node]).difference(set(discovered))
if len(undiscovered) > 0:
for elem in sorted(undiscovered):
queue.append(elem)
discovered.append(elem)
return visited
num_computer = int(sys.stdin.readline())
linked_computer = int(sys.stdin.readline())
_graph = [[] for _ in range(num_computer+1)]
for i in range(linked_computer):
a, b = map(int, sys.stdin.readline().split())
_graph[a].append(b)
_graph[b].append(a)
result = breadth_first_search(_graph, 1)
print(len(result) - 1)
09-31
09-32
09-33
def depth_first_search(graph, row, col): # 6
stack = [(row, col)]
move = [[0, -1], [0, 1], [-1, 0], [1, 0]]
color = graph[row][col] # 10
graph[row][col] = 'X'
while len(stack) > 0: # 13
row, col = stack.pop()
for m in range(4):
next_row, next_col = row, col
next_row += move[m][0]
next_col += move[m][1]
if not check_move(graph, next_row, next_col, color): # 19
continue
stack.append((next_row, next_col)) # 22
graph[next_row][next_col] = 'X'
09-34
def check_move(graph, row, col, color): # 26
if row < 0 or row >= size: # 그림 바깥의 영역
return False
if col < 0 or col >= size: # 그림 바깥의 영역
return False
if graph[row][col] != color: # 31 ; 색깔이 다르면 skip
return False
if graph[row][col] == 'X' # 이미 방문 했으면 skip
return False
return True # 36
size = int(input()) # 39
-
stack을 pop하면 그 노드와 인접한 노드를 stack에 추가해야하는데 이를 상하좌우를 모두 확인해서 그 중 check_move가 false인 경우에 stack에 push하도록 한다.
-
정상인 경우와 적록색약 경우를 나눠서 해야 하기 때문에 새로 만들어진 graph를 정상인 용으로 copy해서 search를 진행하고 다시 적록색약 용도 따로 copy해서 search를 진행해야 하는데 이 때 copy는 deep copy로 진행해야 서로 간섭이 없이 알고리즘 구현이 가능하다.
과제에 알고리즘 설명 및 분석도 포함
# 정답 코드
import sys
import copy
def depth_first_search(graph, row, col):
stack = [(row, col)]
move = [[0, -1], [0, 1], [-1, 0], [1, 0]]
color = graph[row][col]
graph[row][col] = 'X'
while len(stack) > 0:
row, col = stack.pop()
for m in range(4):
next_row, next_col = row, col
next_row += move[m][0]
next_col += move[m][1]
if not check_move(graph, next_row, next_col, color):
continue
stack.append((next_row, next_col))
graph[next_row][next_col] = 'X'
def check_move(graph, row, col, color):
if row < 0 or row >= size:
return False
if col < 0 or col >= size:
return False
if graph[row][col] != color:
return False
if graph[row][col] == 'X':
return False
return True
size = int(sys.stdin.readline())
_graph = []
cnt, cnt_RG = 0, 0 # 일반인의 구역 카운트와 색맹의 구역 카운트
for _ in range(size):
_graph.append(list(sys.stdin.readline().rstrip()))
# 혹은 graph = [[] for _ in range(size)]
# original 그래프 구역을 표시하는 과정에서 훼손될 여지가 있기 때문에 deepcopy
non_RG_blind = copy.deepcopy(_graph)
RG_blind = copy.deepcopy(_graph)
# 색맹의 그래프 전처리 -> Green 을 Red로 변환
for i in range(size):
for j in range(size):
if RG_blind[i][j] == 'G':
RG_blind[i][j] = 'R'
# 구역 카운트 부분 -> 이건 색맹과 일반인이 똑같지만 둘이 다른 그래프를 사용하기 때문에 구별하여 구현
for i in range(size):
for j in range(size):
if not non_RG_blind[i][j] == 'X': # 방문하지 않은 노드라면
depth_first_search(non_RG_blind, i, j) # dfs 적용하여 한 구역을 X 처리
cnt += 1 # dfs가 완료되면 한 구역(R or G or B)이 X가 될 것이므로 카운트 1 증가
for i in range(size):
for j in range(size):
if not RG_blind[i][j] == 'X':
depth_first_search(RG_blind, i, j)
cnt_RG += 1
print(cnt, cnt_RG)
댓글남기기