Algorithm
[이것이 코딩테스트다] DFS(깊이 우선 탐색) / BFS(너비 우선 탐색)
- -
반응형
책의 Chapter5에 등장하는 DFS/BFS에 대해 공부하는 시간이다.
1. 꼭 필요한 자료구조 기초
- 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조
- 스택과 큐
- 삽입(Push) : 데이터 삽입
- 삭제(Pop) : 데이터 삭제
- 스택 : 선입후출 구조 또는 후입선출 구조
- 빈 배열 선언
- append 함수로 데이터 삽입
- pop 함수로 데이터 삭제
stack = []
stack.append(8)
stack.append(0)
stack.append(7)
stack.pop() # pop은 가장 뒤쪽(오른쪽)에 있는 데이터를 꺼냄.
stack.append(6)
stack.append(0)
print(stack)
[8, 0, 6, 0]
- 큐 : 선입선출 구조
- deque 라이브러리 사용 => from collections import deque
- append 함수로 데이터 삽입
- popleft 함수로 데이터 삭제
from collections import deque
queue = deque()
queue.append(7)
queue.append(5)
queue.append(3)
queue.append(1)
queue.popleft()
queue.append(0)
queue.append(7)
queue.popleft()
print(queue)[3, 1, 0, 7]
※ deque 객체를 리스트 자료형으로 바꾸려면 list함수 사용 -> list(queue)
- 재귀함수 : 자기 자신을 다시 호출하는 함수
- DFS와 BFS를 구현하려면 재귀함수도 이해하고 있어야함.
- 재귀함수의 종료 조건은 if문을 활용
def recusrsive_function():
print('재귀 함수를 호출합니다.')
recusrsive_function()
recusrsive_function()RecursionError: maximum recursion depth exceeded while pickling an object해당 오류는 재귀의 최대 깊이를 초과했다는 내용.
2. DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)
- DFS(Depth-First Search) : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
- 그래프 : 노드node(정점vertex) + 간선edge
- 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것
- "두 노드는 인접하다" = "두 노드가 간선으로 연결되어있다"
- 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
- 연결되어 있지 않은 노드는 무한(Infinity)으로 작성
인접 행렬 방식 -
INF = 999999999 # 무한의 비용 선언 9 아홉개 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ]
- 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식
- 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해 저장
인접 리스트 방식 -
# 행(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는 스택 자료 구조 이용
- 구체적인 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문처리.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문처리 하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복.
def dfs(graph, v, visited):
# 현재 노드 방문처리
visited[v] = True
#print(v, end=' ')
stack.append(v)
# 현재 노드와 연결된 다른 노드 중에서 방문하지 않은 곳을 재귀적으로 방문
for i in graph[v]:
if not visited[i]: # 처음에 if visited[v] == "False": 이렇게 했는데 visited 안에 스트링 값이 들어있는게 아니기 때문에 수정
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 스택에 어떻게 쌓이는지 확인하는 용도
stack = []
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
print(stack)
- BFS(Breadth-First Search) : 가까운 노드부터 탐색하는 알고리즘
- 큐 자료구조 이용이 정석
- 구체적인 동작방식
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
from collections import deque
def bfs(graph, start, visited):
# 큐 구현을 위해 deque 라이브러리 사용
queue = deque([start])
print(queue)
# 현재 노드 방문처리
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
# 각 노드가 연결된 정보를 리스트 자료형으로 표현
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
bfs(graph, 1, visited)
3. DFS/BFS 유형의 알고리즘 문제
- 실전문제 음료수 얼려 먹기
- 실전문제 미로 탈출
- Q 15 특정 거리의 도시 찾기
- Q 16 연구소
- Q 17 경쟁적 전염
- Q 18 괄호 변환
- Q 19 연산자 끼워 넣기
- Q 20 감시 피하기
- Q 21 인구 이동
- Q 22 블록 이동하기
반응형
Contents
소중한 공감 감사합니다