[자료구조와 알고리즘 | 파이썬] Graphs - 그래프 자료구조(+약간의 python 개념)

1. Dictionary and Copy in Python

그래프는 자료구조의 꽃이라 불릴 정도로 굉장히 중요하고 그 만큼 어려우며 대부분의 코딩테스트의 문제 중에서 킬러 문제를 담당하는 문제입니다. 그렇기 때문에 이를 제대로 이해해 보기 위해 파이썬의 개념을 먼저 익혀보도록 하겠습니다. 만약 파이썬 개념에 대해서 잘 아시는 분이시라면 중반부로 넘어가셔도 좋습니다!

 

Python Dictionary (파이썬 딕셔너리)

우리가 많이 쓰는 리스트 자료구조에는 순서가 존재했습니다.(ordered)

 

하지만 딕셔너리는 순서가 없는 item의 모음으로 각 item이 key/value 쌍을 갖습니다. (즉, 순서가 없다! - unordered)

• Dictionary is mutable(변경 가능) and iterable(순회 가능).
• Key 값은 unique하고 immutable 해야만 합니다.

마지막줄이 의미하는 것은 튜플(tuple) 객체를 원소로 하는 리스트를 dict() 함수의 인자로 넣으면 그에 맞는 dictionary가 생성된다는 의미입니다.

 

그래서 해당 변수를 콘솔에 찍어보면 아래와 같이 key, value로 정렬되어 나오는 것을 볼 수 있습니다.

>>> print(a)
{'brand': 'Ford', 'model': 'taurus'}

 

또한 접근 방식에 두 가지 방법이 존재합니다.

 

 

a['Key'] vs. a.get('Key')

내가 찾으려는 data가 기존의 dictionary에 없는 경우에 곧바로 key값을 통해 그 딕셔너리에 접근하면 오류가 발생합니다.

 

하지만 딕셔너리의 get함수로 접근하는 경우에는 오류가 발생하지 않습니다.

 

그래서 새로운 key 값에 어떠한 value로 초기화를 시킨다면 오류가 발생하지 않고 딕셔너리에 key, value 쌍을 저장하는 것이 가능합니다.

 

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

 

immutable한 item만 가질 수 있기 때문에 set에 리스트는 집어 넣지 못합니다. 즉 {} 와 같은 중괄호 안에 바로 리스트를 넣는 것이 불가능한 것입니다.

>>> 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을 전달할 수 있습니다.

• 이 경우 리스트를 set 타입으로 변환하는 것이기 때문에 가능한 것입니다.

 

set은 집합을 의미하기 때문에 항상 순차적으로(1,2,3)과 같이 정렬되어 나오는 것이 아닙니다. {3,2,1} 이런식으로도 나올 수 있고, {2,1,3} 이런 식으로도 나올 수 있는 것입니다.

따라서 순서가 중요한 것이 아니라 어떤 item들이 들어있는가가 중요한 것입니다.

• unordered collection이기 때문

 

• 비어 있는 set을 만드려면 반드시 set()을 사용해야 합니다.
  • a = {} 는 빈 dictionary를 만드는 것이기 때문.
• update() 함수를 호출할 때는 그 안의 인자로 반드시 iterable object를 넘겨주어야 합니다.
  • list, tuple, set, string, ...
• discard vs. remove
  • 제거하려는 item이 set에 없는 경우에 discard를 사용하면 error가 발생하지 않지만 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)

 

 

파이썬에는 3가지 방식의 copy가 존재합니다.

Copy: Assignment using '=' operator

첫번째는 '=' 연산자를 사용한 할당입니다.

위 과정을 거치게 되면 b랑 a는 같은 object를 가리키고(reference) 있기 때문에 두 변수의 id도 같은 것입니다.

 

만약 한 object의 내용을 바꾸면 양쪽이 같은 객체를 가리키고 있는 것이기 때문에 같이 update 됩니다.

a[2] = 9 하기 전

a[2] = 9 이후

 

a[2] = 9를 하면 동그라미로 표시한 integer object는 immutable(그 안의 value가 바뀔 수 없음)이기 때문에 9라는 integer object가 하나 생겨서 2번 index가 그 object를 가리키게 되는 것이고 a라는 리스트 객체는 mutable(그 안의 값을 바꿈)이기 때문에 a와 b는 계속해서 똑같은 list object를 가리키고 있을 것이입니다.

 

따라서 기존의 리스트에 값을 추가하는 것이기 때문에 id는 그대로 일 것이고 b는 여전히 a와 같은 객체를 가리키고 있기 때문에 두 값을 찍어보면 a, b 둘 다 9가 추가된 리스트를 출력한 것입니다.

 

여기서 3의 값을 가지고 있는 integer object는 더 이상 referencing 되고 있지 않게 되기 때문에 garbage variable이 됩니다.

 

만약 리스트에서 3의 값을 다시 리스트 원소 중 하나로 넣는다고 해도 다시 새로운 3의 값을 가지는 integer object를 만들어내서 그 값을 가리키지 저 버려진 garbage variable을 가리키지는 않는 것입니다.

 

Copy: shallow copy (얕은 복사)

Copy에는 얕은 복사와 깊은 복사가 존재합니다. 이는 굉장히 헷갈리는 개념으로 잘 알아두시면 좋습니다.

파이썬 copy 모듈

파이썬 copy 모듈에서는 얕은 복사와 깊은 복사를 모두 지원하며 copy 함수가 얕은 복사를 해 주는 기능을 합니다.

 

이는 리스트 object가 copy 되면서 새로운 object가 하나가 별도로 생겨나는 것입니다.

그러나 그 object 안에 딸려 있는 애들(integer object)까지 copy하지는 않습니다. 이 부분이 되게 중요한 포인트입니다.(no recursion)

 

그래서 a 형태를 복사하여 b에 할당해 준 것이기 때문에 b가 가리키는 object는 a와 다르기 때문에 둘의 id 또한 다른 것입니다.

a[2] = 9 하기 전 모습

a[2] = 9 이후 모습

 

 

또한 위 코드를 보면 b[2][0] = 9는 integer object를 바꾸는 것이 아니라 list의 원소를 바꾸는 것이기 때문에 mutable한 객체를 바꾸는 것이고, 이는 별도의 object를 따로 생성하지 않습니다.

따라서 a 리스트의 내용을 공유 하고 있던 리스트의 원소값을 바꾼 것이기 때문에 a를 출력해 보아도 b와 같이 변경된 결과가 나오는 것을 볼 수 있습니다.

b[2][0] = 9 하기 전 모습

b[2][0] = 9 이후 모습

 

shallow copy(얕은 복사)를 사용하는 이유는 memory 절약과 operation의 신속함을 위해서 입니다.

 

다음 그림은 new object를 만드는 방식의 copy 모듈을 사용했을 때의 그림입니다.

 

 

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)

case1: mutable 객체 안에 mutable 객체가 포함된 경우

 

 

case 2: immutable 객체 안에 mutable 객체가 포함된 경우

ori = [1,2]
a = (ori, 3)
b = copy.copy(a)
c = copy.deepcopy(a)

case 2: immutable 객체 안에 mutable 객체가 포함된 경우

 

case 3: immutable 객체 안에 immutable 객체가 포함된 경우

ori = (1,2)
a = (ori, 3)
b = copy.copy(a)
c = copy.deepcopy(a)

case 3: immutable 객체 안에 immutable 객체가 포함된 경우

 

case 4: mutable 객체 안에 immutable 객체가 포함된 경우

ori = (1,2)
a = [ori, 3]
b = copy.copy(a)
c = copy.deepcopy(a)

case 4: mutable 객체 안에 immutable 객체가 포함된 경우

요약

1. deep copy target이 mutable 일 경우
   - target : 원본과 같은 참조
   - target의 포함된 객체 중 mutable 객체는 새로운 사본을 생성
   - target의 포함된 객체 중 immutable 객체는 원본과 같은 참조를 가짐
2. deep copy target이 immutable 일 경우
   - target의 포함된 객체 중 mutable 객체가 있으면 target은 새로운 사본을 생성
   - target의 포함된 객체 중 mutable객체가 없다면 target은 원본과 같은 참조를 가짐
3. shallow copy target이 mutable 일 경우
   - target : 새로운 사본을 생성
   - target의 포함된 객체 : 원본과 같은 참조를 가짐
4. shallow copy target이 immutable 일 경우
   - target : 원본과 같은 참조를 가짐
   - target의 포함된 객체 : 원본과 같은 참조를 가짐
5. immutable로만 구성된 객체일 경우
   - 수정 불가하므로 새로운 공간을 만들지 않는 것으로 예상하며, "=" (Assignment)와 같게 동작합니다.
   - deep, shallow copy 동일 함.
6. 사용자 class 같은 개념으로 적용됨.

 

 

2. Graph and its Representations(그래프 자료구조와 표현방법)

그렇다면 이제 그래프를 배워보도록 하겠습니다.

Graphs

graph는 vertice들 간 연결을 형성하는 vertices(정점, 꼭짓점, 노드)와 edges(간선, 모서리)의 집합입니다. 더 형식적인 접근법에서, 그래프 G는 vertice들의 집합 V와 edge들의 집합 E의 순서쌍이며, 형식적인 수학 표기법에서 G = (V, E)와 같이 주어집니다.

미로(maze)를 생각해 봤을 때, 길 마다의 교차 지점을 노드(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라는 공식이 나옴.

 

신기한 특징

 

그래프 구조

Definition (정의)

• 그래프에서 하나의 경로(path)는 edges에 의해 연결된 vertices의 시퀀스이다. 
  • 노드에서 노드까지의 특정 path의 갯수는 이론상 무한대이다.(왔던 길을 다시 갈수 있다는 가정 하에)
• 간단한 경로(simple path)는 반복된 vertice를 지나지 않는 하나의 경로이다.
  
  • 즉, 한 노드를 두 번 지나지 않는 path.
• 사이클(cycle)은 적어도 하나의 첫번째와 마지막 vertices가 같은 edge를 가진 경로이다. 
  
  • 한 노드에서 출발하여 다시 그 노드로 돌아와서 폐곡선을 만드는 path.
  • 한 노드를 여러번 지날 수 있기 때문에 이론상 무한의 갯수를 가짐.
• 간단한 사이클(simple cycle)은 반복된 edges나 vertices가 없는 사이클이다.(첫 번째 vertice과 마지막 vertice의 필수적인 반복은 제외) 
  • 한 노드를 두 번 지나지 않는 cycle.
• cycle이나 path의 length는 그것의 edge의 개수로 정의된다.
• 그래프의 모든 vertice에서 다른 모든 vertice으로 가는 경로가 있으면 그래프가 연결된다.
• 연결되지 않은 그래프는 최대 연결 하위 그래프(maximal connected subgraphs)인 연결된 구성 요소의 집합으로 구성된다.
• degree(차수): 한 노드에서 다른 노드로 갈 수 있는 가지(edge)의 수
  • 어떤 노드에서 연결된 link의 갯수

• 트리(tree)는 acyclic connceted graph(cycle없이 연결된 그래프)이다. 
• 트리의 disjoint set(서로소 집합)은 forest라고 불린다. 
  • 즉, tree가 모인 구조를 forest라고 한다.

 

---

 

예를 들어, vertice V가 있는 그래프 G는 다음의 다섯 가지 조건 중 하나를 만족하는 경우에만 트리입니다.

• G가 V-1개의 간선을 갖고 cycle이 없다.
• G가 V-1개의 간선을 갖고 연결되어 있다.
• G는 연결되었지만, 아무 간선 하나를 제거하면 연결이 즉시 끊어진다다.
• G는 cycle이 없지만 아무 간선 하나를 추가하면 cycle이 생성된다. 
  • 어느 두 노드를 연결하면 cycle이 되어 버림.
• 정확히 하나의 simple path가 G의 각 정점 쌍을 연결한다.

위 다섯 문장은 다 같은 말이며, 이 중 하나만 만족해도 graph인 것이다.

 

Directed graphs (방향 그래프)

directed graph에서 간선(edge)은 화살표를 통해 그래프의 두 노드 간 연결 방향에 대한 정보를 제공합니다.

 

• Undirected graph(비방향 그래프)
  • 말 그대로 edge에 방향이 없는 것들로 이루어진 graph
• In-degree:
  • 그 노드로 들어오고 있는 link의 갯수
• Out-degree:
  • 그 노드로부터 밖으로 나가고 있는 link의 갯수
• (directed) path
• (directed) cycle

 

Weighted graphs (가중치 그래프)

weighted graph는 그래프의 edges와 관련된 숫자 가중치를 갖는 그래프입니다. 방향 그래프 또는 방향 그래프가 될 수 있습니다. 이 수치는 그래프의 목적에 따라 거리 또는 비용을 나타내는 데 사용될 수 있습니다.

 

해당 그래프는 directed 이든 undirected 이든 상관 없습니다.

위 예제에서 A-D와 A-B-C-D 는 두 가지의 다른 경로를 표현합니다.

• 노드를 무조건 적게 거친다고 좋은 path라고 볼 수 없는 것이다.
• 노드를 지난 개수는 A-D가 더 적지만 노드를 지나면서 발생한 cost가 A-B-C-D보다 더 많이 든다.

 

Graph representations (그래프 표현)

그래프 정보를 파이썬으로 표현(저장)하는 방법에는 여러가지 방식이 존재합니다.

 

그래프 G = (V, E)를 표현하는 두 가지 표준 방식을 선택할 수 있습니다.

• 인접 리스트(adjacency list) 또는 인접 행렬(adjacency matrix)의 모음을 사용할 수 있다.

이는 방향 그래프와 방향 그래프 모두에 적용됩니다.

 

1. 인접리스트 표현은 sparse graph(밀도 낮은 그래프)를 표현하기 위한 compact한 방식을 제공합니다.

• those for which |E| is much less than |V|²

 

2. 그러나 그래프가 밀도가 높을 때(dense graph) 우리는 인접 행렬 표현을 선호할 수 있습니다.

• |E| is close to |V|²
• 혹은 주어진 두 vertice을 연결하는 edge가 있는지 빨리 알 수 있어야 할 때.

 

Adjacency lists (인접 리스트)

이웃하고 있는 노드들을 리스트에 저장하여 그래프를 표현하는 방식입니다.

 

중요한 점은 이웃이라는 워딩(wording)의 의미가 해당 노드로 들어올 수 있는 노드를 의미하는 것입니다. 그래서 undirected라면 상관이 없겠지만 directed graph인 경우 이 점을 유의하여야 합니다.

 

• key: 노드(A, B, C, E, F)
• value: key 노드와 이웃하고 있는 노드들의 리스트

따라서 파이썬에서 key, value 쌍을 저장할 수 있는 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(이웃)이 적다.

 

또한 노드의 이름이 숫자로 되어있는 경우에 굳이 앞에서처럼 dictionary를 사용할 필요없이 key가 index인 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로 접근할 수 있도록 한 것이다. ('1번 인덱스 - 1번 노드', '2번 인덱스 - 2번 노드', ....)

 

Adjacency matrices (인접 행렬)

dense(빽빽한) graph에서 효율적인 방법인 행렬을 사용한 방식입니다.

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 (그래프 알고리즘)

Graph Traversals (그래프 순회)

그래프 순회란 이미 방문한 노드 또는 정점과 방문하지 않은 노드를 추적(tracking)하면서, 그래프의 모든 vertice를 방문하는 것을 의미합니다.

 

즉 두 문장으로 핵심을 정리하면 아래와 같습니다.

• graph traversal: 그래프의 모든 노드를 방문하는 것
• 어느 노드를 방문했는지 기록

 

그래프 순회 알고리즘은 가능한한 최소 시간 안에 그래프의 모든 노드를 순회하는 경우에 효율적입니다.

또한 이는 많은 근본적인 문제에 답을 하는 데 매우 중요합니다.

 

그래프에서 한 vertice에서 다른 vertice로 도달하는 방법과 그래프의 A에서 B vertice 까지의 경로 중 어느 것이 최선의 선택인지를 결정하는 데 굉장히 유용할 수 있습니다.

 

 

다음 섹션에서 두 가지 중요한 그래프 순회 알고리즘에 대해 알아볼 것입니다:

• breadth-first search(BFS): 너비 우선 탐색
• depth-first search(DFS): 깊이 우선 탐색

 

이는 tree 구조를 배웠을 때 나왔던 개념으로 graph는 tree와 다르게 left/right child 개념이 있지 않기 때문에 inorder, postorder, preorder는 없습니다.

 

 

Breadth-first search(BFS): 너비 우선 탐색

BFS에서는 queue 자료구조를 사용합니다.

 

큐에 대한 설명은 아래 링크를 참조하세요.

[자료구조와 알고리즘] Stack and Queues (스택 & 큐)

 

너비 우선 순회 알고리즘은 그래프에서 너비(폭) 방향으로 동작합니다.

• 큐 자료 구조가 그래프에 방문 되어지는 정점들의 정보를 저장하는 데 사용됩니다.

 

동작 방식

예제를 통해 동작 방식을 살펴보겠습니다.

 

시작 노드인 A노드에서 출발합니다. 먼저 노드를 방문한 다음, 이웃 혹은 인접한 모든 정점들을 찾습니다.

 

위 그래프를 A노드에서 시작하여 BFS로 순회를 하면 다음과 같은 경우의 수들이 나올 수 있습니다.

• A-E-C-B-D
• A-C-E-B-D
• A-B-C-E-D

근데 만약 학교 시험이거나 아무 조건이 없거나 '순회한 알파벳 순서를 적으시오' 와 같이 문제가 나온다면 1,2,3 번 중 마지막 3번 경우처럼 적으면 좋습니다.

• 편리를 위해 알파벳 순서대로

 

discovered: queue에 한번이라도 들어갔던 노드를 다시 queue에 넣는 것을 방지하기 위해서 discovered 리스트에 저장을 해 둡니다.

 

visit: 방문한 노드의 순서를 기록(record)합니다. 즉, 이것이 탐색의 최종 결과로 볼 수 있습니다.

 

아래는 다른 예시로 BFS 과정을 한 눈에 볼 수 있습니다.

되도록 알파벳 순서로 인근한 노드를 큐에 집어넣도록 합니다.

 

또 다른 예시

그래프 저장 방식 -> key 값이 문자열이고 sparse 그래프이기 때문에 딕셔너리를 사용한 인접리스트를 활용합니다.

# the graph in page 208 
graph1 = {       
    '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')  
print(*ans, sep='-')

실행 결과

 

breadth_first_search 함수 구현

from collections import deque 


def breadth_first_search(graph, root):
    #sequence of visited nodes
    visited = []
    discovered = []
    queue = deque([root])
    discovered.append(root)

    while len(queue) > 0: # queue에 뭐라도 있으면 반복
        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 # 22

• 우리는 stack과 queue를 배우면서 두 자료구조 모두 collections 모듈의 deque 클래스를 사용하면 굉장히 유용하다는 사실을 배웠습니다.
• set(graph[node]).difference(set(discovered))의 의미: 어떤 노드와 인접한 노드(graph[node])중에서 discovered 된 것을 제외한 것이 undiscovered에 저장된다.
  • graph[node] 는 node의 인접 노드들의 정보가 담겨있음
  • 이는 두 집합의 차집합(difference set)으로 구현했다.
• 그 후 차례차례 queue에서 pop한 것이 방문한 것이므로 result 리스트(visited)에 들어간다.

 

 

Depth-first search(DFS): 너비 우선 탐색

DFS는 머릿속에 stack을 그리고 생각하면 편합니다!

 

이름에서 알 수 있듯이 DFS 알고리즘은 그래프의 특정 경로의 깊이를 통과한 후에 너비를 통과합니다. 따라서 자식 노드는 형제 노드보다 먼저 방문 됩니다.

 

스택 자료구조가 이 DFS 알고리즘을 구현하는 데 사용됩니다.(BFS와는 반대)

 

DFS도 역시 discovered라는 이미 발견된적이 있는지를 저장하는 리스트가 존재합니다.

인근한 노드 중에서 발견되지 않는 노드를 stack에 추가해 가면서 탐색을 진행합니다.

• A-B-D-C-E

 

스택에서 꺼냈다(pop)는 것은 그 노드를 방문한 것이며, 알파벳 순서를 지키기 위해서 한 노드와 이웃한 노드를 stack에 집어 넣을 때 알파벳 반대 순서로 넣습니다.

즉, A, B, C 순서대로 stack에서 빼야하기 때문에 가장 밑 바닥부터 C, B, A 순서로 깔리기 위해서는 애초에 인접 노드를 스택에 넣을 때는 알파벳 역순으로 넣어야 하는 것입니다.

 

 

알파벳 역순으로 넣지 않은 예시

사실 어떻게 하든 상관은 없지만 헷갈릴 여지를 없애기 위해서 위 그림과 같이 하지말고 되도록 알파벳 순서로 탐색할 수 있도록 스택에 집어넣을 때는 알파벳 역순으로 집어넣기로 합니다.

 

 

Example

앞선 BFS 예시와 마찬가지로 그래프 저장 방식은 key 값이 문자열이고 sparse 그래프이기 때문에 딕셔너리를 사용한 인접리스트를 활용합니다.

# the graph in page 211
graph2 = {
    'A': ['B', 'S'],
    'B': ['A'],
    'S': ['A', 'G', 'C'],
    'D': ['C'],
    'G': ['S', 'F', 'H'],
    'H': ['G', 'E'],
    'E': ['C', 'H'],
    'F': ['C', 'G'],
    'F': ['D', 'S', 'E' ,'F']
}

ans = depth_first_search(graph2, 'A')
print('-'.join(ans))

실행 결과

 

depth_first_search 함수 구현

def depth_first_search(graph, root): 
    #sequence of visited nodes
    visited = []
    # nodes which are discovered & stacked
    discovered = []
    stack = [root]
    discovered.append(root)

    while stack: # stack이 비지 않았으면 (= len(stack))
        node = stack.pop()
        visited.append(node)
        undiscovered = set(graph[node]).difference(set(discovered))

        if undiscovered: 
            for elem in sorted(undiscovered, reverse=True):
                stack.append(elem)
                discovered.append(elem)

    return visited

발견되지 않은 노드를 스택에 넣고 discovered에도 넣는데 이때 앞서 말했던 대로 알파벳 역순서대로 스택에서 빼고 싶기 때문에 reverse=True 로 설정해 주었습니다.

 

Example: BFS and DFS

 

s로부터 도달 가능한 임의의 노드 v에 대해, 너비 우선 트리(BFS)에서 s에서 v로 가는 단순한 path는 G라는 그래프에서 s to v 로 가는 가장 짧은 path 즉, 가장 적은 숫자의 edges를 포함하는 path입니다. (the shortest path algorithm)

 

 

 

관련된 문제

2606번: 바이러스

 

• 1-2-5-3-6 : BFS
  • 1번 컴퓨터는 숙주이므로 제외시켜야 하기 때문에 (len() - 1)이 최종 정답이다.

 

# 정답 코드
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)

 

 

 

백준 10026번 적록색약

10026번: 적록색약

 

 

 

 

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: #색깔이 다르면 skip
        return False
    if graph[row][col] == 'X' # 이미 방문 했으면 skip
        return False

    return True

size = int(input())

 

 

• 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)