DFS / BFS , Graph Structure

"Stack, Queue, Recursive Func는 DFS / BFS에서 가장 중요한 개념"

https://cord-ai.tistory.com/156

Stack, Queue, Recursive Function

그래프 구조, Graph Structure

- 노드 Node, 간선 Edge로 표현됨(이 때 노드를 정점 Vertex라고도 말한다)

- 예를 들어 노드 == 도시, 간선 == 도로

- 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다.

- 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다 'Adjacent'라고 표현함

 

그래프 표현 방식

1. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

- 다른 언어의 배열(Array)을 파이썬에서는 리스트 자료형으로 표현할 수 있으므로 파이썬은 인접 행렬을 리스트로 구현한다.

2. 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

# 1. 인접 행렬, Adjacency Matrix

INF = 9999999 # 무한의 비용 선언

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)
[[0, 7, 5], [7, 0, 9999999], [5, 9999999, 0]]

# 2. 인접 리스트, Adjacency List 
# - 전통적인 프로그래밍 언어에서의 배열과 연결 리스트의 기능을 모두 기본으로 제공
# - 파이썬으로 인접 리스트를 이용해 그래프를 표현하고자 할 때에는 단순히 2차원 리스트를 이용하면 됨

graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))

graph[1].append((0,7))
graph[2].append((0,5))

print(graph)
[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

 

"인접 행렬과 인접 리스트의 차이"

- 메모리 측면에서 보자면 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비된다.

- 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.

* But 이와 같은 속성 때문에 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. = 인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문

ex) 한 그래프에서 노드 1과 노드 7이 연결되어 있는 상황
인접 행렬 = graph[1][7]
인접 리스트 = 노드 1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야한다.

그러므로 특정한 노드와 연결된 모든 인접 노드를 순회해야하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다.

Depth-First Search, DFS

- "깊이 우선 탐색", 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 = FILO, Stack 자료구조 이용함

- 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘

= 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복

'방문 처리'는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미
'방문 처리'함으로써 각 노드를 한 번씩만 처리할 수 있다.

Breadth First Search, BFS

- "너비 우선 탐색", 가까운 노드부터 탐색하는 알고리즘 = FIFO, Queue 자료구조 이용

- DFS와 반대

- 인접한 노드를 반복적으로 Queue에 넣도록 알고리즘 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

- 보통 DFS보다는 BFS가 빠르다 정도로만 기억(= 재귀 함수로 DFS 구현시 컴퓨터 시스템의 특성상 실제 프로그램의 수행 시간은 느려질 수도 있다고 한다.)

1. 탐색 시작 노드를 Queue에 삽입하고 방문 처리
2. Queue에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 Queue에 삽입하고 방문처리3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복

	DFS	BFS
동작 원리	Stack	Queue
구현 방법	재귀 함수	Queue 자료 구조

참조 영상

https://youtu.be/_hxFgg7TLZQ

<이것이 취업을 위한 코딩테스트다 with 파이썬>

DFS / BFS 문제 풀이(설명 참조)

https://devmath.tistory.com/19

[DFS/BFS] 실전 문제 <4> 미로 탈출 / 이것이 취업을 위한 코딩테스트다 with 파이썬 / 파이썬 Python