1. DFS & BFS 를 배우기 전 알아두어야 할 자료구조 기초
- 스택(Stack)
- 스택은 박스 쌓기에 비유할 수 있다.
후입선출(LIFO)이므로 나중에 들어온 데이터가 먼저 나가는 구조이다. - 스택은 list를 활용해 표현할 수 있다.
append()함수는삽입을 의미하고,pop() 함수는 가장 나중에 들어온 원소를삭제하는 것을 의미한다.stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() # 결과값 : [5, 2, 3, 1]
- 스택은 박스 쌓기에 비유할 수 있다.
- 큐(Queue)
- 큐는 대기 줄에 비유할 수 있다.
선입선출(FIFO)이므로 먼저 들어온 사람이 먼저 나가는 구조이다. - 파이썬으로 큐를 구현할 때는
collections 모듈에서 제공하는deque 자료구조를 활용하는 것이 좋다.- 이를 이용하면 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이고 queue 라이브러리를 이용하는 것보다 간단하기 때문이다.
- deque 객체를 리스트 자료형으로 변경하고자 한다면
list()메소드를 활용하면 된다. append()함수는삽입을 의미하고,popleft() 함수는 가장 먼저 들어온 원소를삭제하는 것을 의미한다.from collections import deque # 큐 구현을 위해 deque 라이브러리 사용 queue = deque() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) queue.popleft() # 결과값 : deque([3, 7, 1, 4])
- 큐는 대기 줄에 비유할 수 있다.
- 재귀 함수
- 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미
- 재귀 함수를 문제 풀이에서 사용할 때는 반드시
종료 조건을 명시해야 한다. - 대표적인 예시로는 팩토리얼 문제가 있다.
def factorial_recursive(n): if n <= 1: # n이 1 이하인 경우 1 반환 return 1 return n * factorial_recursive(n-1) # n! = n * (n - 1) 코드를 그대로 작성
2. DFS(Depth-First Search, 깊이 우선 탐색)
- 말 그대로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 부름
- 두 노드가 간선으로 연결되어 있다면
두 노드는 인접하다라고 표현
- DFS는
스택을 이용하는 알고리즘이므로,재귀 함수를 이용했을 때 매우 간결하게 구현 가능 - 동작 과정
-
탐색 시작 노드를 스택에 삽입하고 방문 처리
-
스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
-
2번의 과정을 더 이상 수행할 수 없을 때까지 반복
def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 각 노드와 연결된 정보를 리스트 자료형으로 표현(2차원 리스트) graph = [ [], [2, 3, 8], # 1 [1, 7], # 2 [1, 4, 5], # 3 [3, 5], # 4 [3, 4], # 5 [7, 8], # 6 [2, 6, 8], # 7 [1, 7] # 8 ] # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트) visited = [False] * 9 dfs(graph, 1, visited)
-
- 예시 : 음료수 얼려 먹기
- ❓ 문제 : N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1이다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수는?
- 4 x 5 얼음 틀일 경우, 아이스크림이 총 3개 생성된다.
n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) def dfs(x, y): # 주어진 범위에 벗어나는 경우 즉시 종료 if x <= -1 or x >= n or y <= -1 or y >= n: return False # 현재 노드를 아직 방문하지 않았다면 if graph[x][y] == 0: # 해당 노드 방문 처리 graph[x][y] = 1 # 상, 하, 좌, 우의 위치도 재귀적으로 호출 dfs(x-1, y) dfs(x, y-1) dfs(x+1, y) dfs(x, y+1) return True return False result = 0 for i in range(n): for j in range(m): if dfs(i, j) == True: result += 1 print(result)
3. BFS(Breadth-First Search, 너비 우선 탐색)
- 가까운 노드부터 탐색하는 알고리즘, DFS와 반대이다.
- 선입선출 방식인
큐 자료구조를 이용하는 것이 정석,deque라이브러리를 사용하는 것이 좋음 - 일반적인 경우 수행 시간은 DFS 보다 좋은 편
- 동작 과정
-
탐색 시작 노드를 큐에 삽입하고 방문 처리
-
큐에서 노드를 꺼내 해당 노드의 인접 노드 중, 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
-
2번의 과정을 더 이상 수행할 수 없을 때까지 반복
from collections import deque def bfs(graph, start, visited): queue = deque([start]) visited[start] = True # 현재 노드를 방문 처리 # 큐가 빌 때까지 반복 while queue: # 큐에서 하나의 원소를 뽑아 출력 v = queue.popleft() print(v, end=' ') # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입 for i in graph[v]: if not visited[i]: queue.append(i) visited[i] = True # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트) graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트) visited = [False] * 9 bfs(graph, 1, visited)
-
4. 요약
| DFS | BFS | |
|---|---|---|
| 동작 원리 | 스택 | 큐 |
| 구현 방법 | 재귀 함수 사용 | 큐 자료구조 이용 |
| 적합한 유형 | 검색 대상 그래프가 크거나 경로의 특징을 저장해두어야 하는 문제 (ex) 각 정점에 숫자가 적혀있고, a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제) | 최단거리 구할 때 이용(ex) 미로찾기) |
Back-End Developer 🌱