(이코테)1. DFS/BFS 개념 복습
Object
자료구조 기초
탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조 활용, deque는 스택과 큐의 장점을 모두 채택한 것으로, 데이터 입출력 속도가 빠르고 queue 라이브러리보다 간단하다.
재귀함수: 자기 자신을 다시 호출하는 함수
1
2
3
4
5
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()
위의 사례가 가장 간단한 재귀함수(단, 종료 조건이 없어서 무한히 실행됨) 재귀함수의 장점은 코드가 더 간결해진다는 점; 재귀 함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문에 간결해짐 → 다이나믹 프로그래밍으로 이어짐**
DFS(Depth-First Search , 깊이 우선 탐색)
그래프 표현 방식
Node, Edge로 표현되며 이 때 노드를 Vertex라고도 말한다.
프로그래밍에서 그래프를 표현하는 방법은 두 가지가 있는데, 인접 행렬과 인접 리스트가 그것이다.
- 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식
1
2
3
4
5
6
7
8
9
10
INF = 99999999
# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph)
인접 리스트 방식에서는 ‘인접 리스트’ 자료구조를 이용해 구현하는데, 파이썬은 기본 자료형인 리스트 자료형이 연결 리스트 기능을 수행할 수 있음 ⇒ 단순 2차원 리스트로 구현하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# row=3인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]
# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))
# 노드 1에 연결된 노드 정보
graph[1].append((0, 7))
# 노드 2에 연결된 노드 정보
graph[2].append((0, 5))
print(graph)
** 서로 다른 방식을 비교할 때, 코테 시각으로 접근하는 방식은 메모리와 속도 측면에서 비교하는 것이다.
메모리 측면: 인접 행렬 방식은 노드 개수 많을 수록 불필요한 메모리 낭비 늘어남
속도 : 두 노드의 연결 여부에 대한 정보를 얻는 속도가 느림(연결된 정보만 저장하기 때문에 일일이 조회)
DFS 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드(가장 마지막에 들어온 노드)가 미방문 인접 노드를 가진다면, 인접 노드를 스택에 넣고 방문 처리 / 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄(pop)
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
일반적으로 인접한 노드 중 방문하지 않은 노드 여러 개 있으면 번호 낮은 순서부터 처리한다.
시간복잡도
데이터 개수가 N개인 경우 $O(N)$
위의 예시에서는 스택을 활용하지만 실제 구현 과정에서는 스택을 사용하지 않아도 된다.
BFS(Breadth First Search, 너비 우선 탐색)
인접한 노드를 반복적으로 큐에 넣도록 해서, 먼저 들어온 것이 먼저 나가고, 가까운 노드부터 탐색을 진행한다.
BFS 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드 꺼내 해당 노드의 미방문 인접 노드를 모두 큐에 삽입 후 방문 처리
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
시간복잡도
$O(N)$
재귀 함수로 DFS를 구현하면 CS 동작 특성상 실제 프로그램의 수행 시간은 느려질 수 있기 때문에 스택 라이브러리 이용해 시간 복잡도 완화 테크닉이 필요할 수도 있다.
** 코테에서는 DFS보다 BFS 구현이 조금 더 빠르게 동작한다.