[동빈북] DFS와 BFS

김우경·2020년 11월 15일
0

1. 필요한 자료구조

스택

  • FILO
  • 별도의 라이브러리 필요 x
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)

print(stack)
print(stack[::-1]) #최상단 원소부터

  • FIFO
  • deque 라이브러리 이용 → 큐와 스택의 장점 모두
from collections import 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()

print(queue)
print(queue.reverse()) #나중에 들어온 순서대로

재귀함수

  • 내부에서 스택 자료구조 이용

    → 가장 마지막에 호출한 함수가 먼저 끝나야 앞의 함수호출 종류

def factorial_iterative(n):
	result = 1
	for i in range(1, n+1):
		result += i
	return result

def factorial_recursive(n):
	if n <= 1:
		return 1
	return n*factorial_recursive(n-1)

2. 탐색 알고리즘 DFS/BFS

그래프의 표현

  1. 인접 행렬

    : 2차원 배열로 그래프의 연결 관계 표현

    → 연결되지 않은 노드끼리의 비용을 무한대로

    INF = 999999999
    graph = [
    	[0, 7, 5],
    	[7, 0, INF],
    	[5, INF, 0]
    ]
  2. 인접 리스트

    : 리스트로 그래프의 연결 관계를 표현하는 방식

    graph = [[] for _ in range(3)]
    
    graph[0].append(1,7)]
    graph[0].append(2,5)]
    graph[1].append(0,7)]
    graph[2].append(0,5)]

DFS

  • 스택 이용 → 재귀

  • 동작 과정

    : 탐객 시작 노드를 스택에 삽입, 방문 처리

    → 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 해당 노드 스택에 넣고 방문, 없으면 스택에서 최상단 노드 pop

    → 2번 과정을 반복

	def dfs(graph, v, visited):
		#현재 노드 방문처리하기
		visitied[v] = True
		print(v, end=' ')
	
		#현재 노드와 연결된 다른 노드를 재귀적으로 방문하기
		for i in graph[v]:
			if not visited[i]:
				dfs(graph, i, visited)

graph = [
	[],
	[2, 3, 8],
	[1, 7],
	[1, 4, 5],
	[3, 5],
	[3, 4],
	[7],
	[2, 6, 8],
	[1, 7]
]

visited = [False]*9
dfs(graph, 1, visited)
  • 장점

    -현 경로상의 노드를 기억하므로 적은 메모리 사용

    -찾으려는 노드가 깊은 단계에 있는 경우 bfs보다 빠름

  • 단점

    -얻은 해가 최단 경로라는 보장이 없음 → DFS는 해에 도착하면 탐색 종료함

    -해가 없는 경로에도 끝까지 탐색

BFS

  • 가까운 노드부터 탐색

  • queue 이용해서 구현

  • 동작과정

    : 탐색 시작 노드를 큐에 삽입, 방문처리

    → 큐에서 노드 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드 모두 큐에 삽입, 방문처리

    → 2번 과정을 반복

  • O(N)

    → 실제 수행 시간이 일반적으로 dfs보다 나음

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

graph = [
	[],
	[2, 3, 8],
	[1, 7],
	[1, 4, 5],
	[3, 5],
	[3, 4],
	[7],
	[2, 6, 8],
	[1, 7]
]

visited = [False]*9
bfs(graph, 1, visited)

→ 2차원 배열에서의 탐색 문제는 그래프 형태로 바꿔서 생각하기

  • 장점

    -답이 여러개여도 최단경로임을 보장

    -최단경로가 존재하면 깊이가 무한정 깊어져도 찾을 수 있음

  • 단점

    -경로가 매우 길 경우 메모리 많이 필요

    -해가 없는 유한 그래프의 경우 모든 그래프 탐색 후 실패로 끝남

    -의 경우 답을 찾지도, 끝내지도 못함

DFS와 BFS 무엇을 선택해야 할까?

DFS와 BFS

profile
Hongik CE

0개의 댓글