알고리즘 공부 #3

leejm·2021년 6월 19일
0

DFS / BFS

탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
그 중에서 DFS / BFS를 가장 많이 활용

1. 스택(Stack) : DFS에서 활용

  • 먼저 들어온 데이터가 나중에 나가는 선입후출(FILO)의 자료구조
  • 입구와 출구가 동일한 형태로 프링글스 통을 연상하면 됨
  • 파이썬에선 리스트 자료구조로 삽입(append)/ 삭제(pop) 기능으로 구현

2. 큐(Queue) : BFS에서 활용

  • 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO)의 자료구조
  • 입구와 출구가 모두 뚫린 터널 형태를 연상하면 됨
  • 리스트 자료형을 이용 시 시간 복잡도가 높아서 덱(Deque) 라이브러리 이용
from collections import deque 

# 큐(Queue) 구현을 위해 덱(Deque) 라이브러리 이용
queue = deque()

# 예 : 삽입(5)-삽입(2)-삽입(3)-삽입(7)-삭제()-삽입(1)-삽입(4)-삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

3. 재귀함수 : 자기 자신을 다시 호출하는 함수로 DFS에 많이 사용하는 개념

  • 문제풀이 시에는 종료 조건을 반드시 명시해야 함

  • 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임
    그래서 구현 상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음

    DFS

    깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
    스택 혹은 재귀함수 이용

  1. 탐색 시작 노드를 스택에 삽입하고 방문처리

  2. 스택 최상단 노드 중 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리
    없다면, 스택에서 최상단 노드를 꺼냄

  3. 2번을 수행할 수 없을 때까지 반복

    -예시 그래프- 적은 숫자 노드부터 방문한다고 설정

    [Step 1] 시작 노드인 1을 스택에 삽입 후 방문처리
    [Step 2] 인접 노드 2,3,8 중 가장 작은 2를 스택에 넣고 방문처리
    [Step 3] 최상단 노드의 방문하지 않은 인접 노드 7을 스택에 넣고 방문처리
    [Step 4] 방문하지 않은 인접 노드 중 작은 6을 스택에 넣고 방문처리
    [Step 5] 6을 스택에서 꺼내줌
    [Step 6] 방문하지 않은 인접 노드 8을 스택에 넣고 방문처리
    [Step 7] 반복

    방문 순서 : 1-2-7-6-8-3-4-5

 
def dfs(graph, v, visited) :

	# 현재 노드를 방문 처리
    visited[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

BFS는 너비 우선 탐색이라고 부르며 가까운 노드부터 우선적으로 탐색하는 알고리즘
큐 자료구조를 이용

  1. 탐색 시작 노드를 큐에 삽입하고 방문처리

  2. 큐에서 노드를 꺼낸 후 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 하고 방문처리

  3. 2번의 과정을 수행할 수 없을 때까지 반복

    -예시 그래프- 적은 숫자 노드부터 방문한다고 설정

    [Step 1] 시작 노드인 1을 큐에 삽입 후 방문처리
    [Step 2] 큐에서 1을 꺼내고 인접 노드 2,3,8을 큐에 넣고 방문처리
    [Step 3] 큐에서 2를 꺼내고 방문하지 않은 인접 노드 7을 큐에 넣고 방문처리
    [Step 4] 큐에서 3을 꺼내고 방문하지 않은 인접 노드 4, 5를 큐에 넣고 방문처리
    [Step 5] 반복

    방문 순서 : 1-2-3-8-7-4-5-6

 
from collections import deque

#BFS 메서드 정의
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)
profile
Python Based Backend Engineer입니다. DevOps와 효율적으로 일하는 것에 관심이 있습니다.

0개의 댓글