이코테 2021 - DFS & BFS

재귀함수

 

재귀함수 (Recursive Function) : 자기 자신을 다시 호출하는 함수

def recursive_function():
	print('재귀함수 호출')
    recursive_function()

recursive_function()

> 파이썬에서는 최대 재귀 깊이 제한이 있어, 이를 실행하면 오류메시지가 뜬다.

(RecursiveError : maximum recursion depth exceeded while calling a Python object.)

> 따라서, 재귀함수를 사용할 때는 재귀 함수의 종료조건을 명시하여 반복문이 끝나도록 해야 한다.

 

 

Ex) 팩토리얼문제

# n! = n * (n-1) * (n-2) * ... * 1
def factorial_recursive(n):
	if n <= 1:
            return 1
	return n * factorial_recursive(n-1)

 

Ex) 유클리드 호제법 : 두 개의 자연수에 대한 최대공약수

def gcd(a,b):
    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)

gcd(192, 162)
# 6

 

> 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.

 

> 함수가 재귀적으로 호출이 되면, 컴퓨터 시스템 스택프레임에 함수가 반복적으로 쌓이게 됨.

   마지막으로 호출된 함수가 처리가 된 이후에 이를 불렀던 함수가 처리된다.

> 역으로 생각하면, 스택을 사용해야 할 때, 구현상 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 많다.

 ex) DFS의 간결한 코드를 위해

 

 

 

 

DFS (Depth-First Search)

 

DFS (Depth-First Search, 깊이 우선 탐색) : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

> 스택 자료구조 혹은 재귀함수를 이용

 

<동작과정>

1. 탐색 시작 노드를 스택에 삽입하고 방문처리 하기 (방문처리 = 스택에 넣기?)
2. 스택의 최상단 노드(첫번째 노드)에 (아직) 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리 하기
   만약, 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼내기
3. 2번의 과정을 수행할 수 없을 때까지 반복

Step 0: 그래프 준비 (시작노드 : 1)

Step 1 : 시작노드인 '1'을 스택에 삽입하고 방문처리 함

Step 2: 최상단 노드인 '1'에 방문하지 않은 인접 노드 2, 3, 8 중 작은 것(2)부터 방문처리

2에 인접한 노드 중 방문하지 않은 노드 7을 스택에 넣고 방문처리

7에 인접한 방문하지 않은 노드 중 가장 작은 6을 방문처리

> 깊은 곳을 우선적으로 탐색 

방문하지 않은 인접노드가 없으므로, 스택에서 최상단 노드 6을 꺼냄

Step 3: step2의 과정을 수행할 수 없을 때까지 반복

결과, 스택에 들어간 순서

> 이를 재귀함수로도 구현이 가능하다

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= [
    [],              # 인덱스 0에 대한 내용은 비워두기
    [2, 3, 8],       # 1번 노드와 연결된 노드
    [1, 7],          # 2번 노드와 연결된 노드
    [1, 4, 5],       # 3번 노드와 연결된 노드
    [3, 5],
    [3, 4],          # ...
    [7],
    [2, 6, 8],
    [1, 7]           # 8번 노드와 연결된 노드
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9   # 0번 인덱스는 버리고, 1-8번 노드를 위함 = 0-8까지 9개

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)  # 1번 노드부터 시작

 

 

 

 

 

 

 

BFS(Breadth-Fast Search)

 

BFS(Breadth-Fast Search, 너비 우선 탐색) : 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

> 큐 자료구조를 이용

 

<동작과정>

1. 탐색 시작 노드를 큐에 삽입하고 방문처리 하기
2. 큐에서 노드를 꺼낸뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 하기
3. 2번의 과정을 수행할 수 없을 때까지 반복

Step 0 : 그래프 준비 (시작노드 : 1)

Step 1: 시작노드인 1을 큐에 삽입하고 방문처리

Step 2: 큐에서 노드를 꺼낸 후 (1번 노드), 방문하지 않은 인접 노드(2,3,8)를 큐에 삽입하고 방문처리

마찬가지로 큐에서 2번노드를 꺼내고, 꺼낸 2번노드를 기준으로 방문하지 않은 인접노드 7을 큐에 삽입 후 방문처리

만약, 방문하지 않은 인접노드가 없으면 무시하고 다음과정을 진행

결과, 큐에 들어간 순서

 

> 시작노드인 1번 노드부터 거리가 가까운 순서대로 탐색한 것을 확인할 수 있다.

> 각 연결거리비용이 동일하다는 조건 하에 최단거리 구하기 문제에서 많이 사용된다.

 

from collections import deque

def bfs(graph, i, visited):
    
    # 현재 노드를 방문처리
    queue= deque([i])
    visited[i] = True
    
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v= queue.popleft()
        print(v, end= ' ')
        
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for node in graph[v]:
            if not visited[node]:
                queue.append(node)
                visited[node] = 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 함수 호출
bfs(graph, 1, visited)

> 재귀함수 사용 x

 

 

 

 

아래 영상을 참고하였습니다.