[코딩 테스트] DFS BFS 개념 - 스택 큐 자료구조 재귀함수 기초

DFS BFS란,

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 탐색(Search)이라고 하며,

DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다.

코딩테스트에서 매우 자주 등장하는 유형이다.

 

스택 자료구조

먼저 들어온 데이터가 나중에 나가는 형식(선입후출, LIFO - last in first out)의 자료구조. 입구와 출구가 동일하다.

박스 쌓기 예제를 생각하면 된다.

삽입과 삭제, 두 가지가 있다.

 

파이썬에서는 리스트의 append와 pop을 이용해서, 스택을 구현할 수 있다.

append : 우측에 데이터 붙임

pop : 우측의 데이터 삭제

print(list명[::-1]) 하면 최상단 원소부터 출력 가능하다.(리스트를 거꾸로 출력하는 것)

 

큐 자료구조

먼저 들어온 데이터가 먼저 나가는 형식(선입선출, FIFO - first in first out). 대기열.

터널 모양을 생각하면 된다.

 

덱 자료구조

덱은 Deque, double-ended queue라는 의미로, 스택과 큐의 특성을 모두 갖는 둘을 조합한 형태이다.

즉 양방향으로 넣고, 뺄 수 있다.

 

리스트 자료형으로 큐를 구현하면 시간 복잡도가 높아지는데, 이는 원소를 꺼낸 다음 재정렬하는 과정이 필요하기 때문에 시간 복잡도가 높아지기 때문이다.

따라서, 파이썬에서 큐를 구현하기 위해서는 반드시 이 deque을 import해와서 사용해야 한다. 그래야만 시간 문제를 해결할 수 있다.

from collections import deque

queue = deque()

 

queue.append(5)

queue.popleft() # 가장 왼쪽의 데이터를 꺼낼 때.

queue.reverse() #역순으로 바꿀 수도 있다.

 

재귀 함수

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

파이썬에서는 기본적인 깊이 제한이 있으므로, 따로 재귀 제한을 설정하지 않으면 어느 정도 출력 후 최대 재귀 깊이 초과 메세지가 뜨면서 오류가 발생한다.

코딩테스트에서는 일반적으로 재귀 함수의 종료 조건을 반드시 명시해야 한다.

그래서 함수 무한 호출으로 인한 오류가 발생하지 않도록 해주어야 한다.

 

문제 1. 팩토리얼 구현 예제

n! = n부터 1까지 곱한 결과.

*0!과 1!의 값은 1이다.

 

#점화식을 이용해서 문제를 풀기 때문에 for문 사용 없이 해결할 수 있다!

def factorial_recursive(n):

    if n<=1:

        return 1

    return n * factorial_recursive(n-1) #n!=n*(n-1)을 그대로 코드로 작성

print("재귀적 구현 : ", factorial_recursive(5))

 

 

문제 2. 최대공약수(유클리드 호제법)

두 개의 자연수에 대한 최대공약수를 구하는 알고리즘

유클리드 호제법

-  A>B인 두 자연수 A,B에 대하여 A를 B로 나눈 나머지를 R이라고 하자.

이 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

 

def gcd(a,b):

    if a%b==0:

        return b

    else :

        return gcd(b, a%b)

 

print(gcd(192,162))

 

재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있지만,

오히려 다른 사람이 이해하기 어려울 수 있으니 주의하자.

모든 재귀함수와 반복문은 동일한 기능을 구현할 수 있으므로, 어느 것이 더 유리한지 판단하자.

 

*함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.

그래서 구현상 스택을 사용해야 할 때, 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많다.

대표적으로 DFS를 더 간결하게, 재귀함수로 간단히 구현하기도 한다.

 

DFS (Depth First Search)

깊이 우선 탐색 : 그래프에서 깊은 부분을 우선적으로 탐색한다.

스택 자료구조 혹은 재귀 함수를 이용하며, 구체적으로는 아래와 같다.

 

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

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리.

방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼내기.

이 과정을 더 수행할 수 없을 때까지 반복

방향이 없는 그래프일 때, 인접 노드가 여러개일 때 어떤 노드부터 방문할지에 대한 방문 기준이 필요하다. (기준이 없는 경우도 있으나, 주로 번호가 낮은 인접 노드부터)

 

파이썬에서는 그래프를 표현하기 위해 2차원 리스트를 이용한다.

일반적으로 그래프 번호가 출제되면, 일반적으로 노드 번호가 1부터 시작하는 경우가 많으므로,

인덱스 0에 대한 내용은 비워두고,

인덱스 1부터 해당 노드에 인접한 노드들을 표현할 수 있다.

 

방문 처리를 위해서는 1차원 리스트를 만들어주되,

모든 노드를 False로 처리하여 아직 아무 곳에도 방문하지 않았다는 처리를 해주고,

1번~8번 인덱스를 사용하고 인덱스 0은 사용하지 않기 위해서 9개를 False처리해주자.

 

실제 DFS 함수를 정의하기 위해서는 그래프 정보와 방문처리를 하고, 노드의 번호를 통해서 실행 결과를 얻을 수 있다.

예시 코드)

#2차원 리스트로 각 노드가 연결된 정보를 표현하자.

graph  = [

[],

[2,3,8],

[1,7],

[1,4,5],

[3,5],

[3,4],

[7],

[2,6,8],

[1,7]

]

 

# 1차원 리스트로 각 노드가 방문된 정보를 표현

visited = [False] * 9

 

#DFS 함수 정의 후, 호출

def dfs(graph, v, visited):

    visited[v] = True # 현재 노드를 방문 처리

    print(v, end=' ')

    #현재 노드와 연결된 다른 노드를 재귀적 방문

    for i in graph[v]:

        if not visited[i]:

            dfs(graph, i, visited)

dfs(graph, 1, visited)

 

BFS(Breadth-First Search)

너비 우선 탐색 : 가까운 노드부터 우선적으로 탐색하는 알고리즘.

큐 자료구조를 이용한다.

1. 출발지점, 즉 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중,

방문하지 않은 노드를 모두 큐에 삽입하고, 방문 처리.

더이상 2를 수행할 수 없을 때까지 반복.

 

* DFS에서는 인접하지 않은 노드를 한번씩 넣으면서 다시 방문을 수행했다면,

BFS에서는 해당 시점에서 한 번에 삽입한다는 점이 다르다.

특히 BFS에서는 특정 조건에서의 최단 경로를 구하는 문제에 사용된다.

큐 자료구조가 쓰이기 때문에 각 프로그래밍 언어마다 큐 자료구조가 어떻게 쓰이는지 숙지해야 한다.

 

시작 지점으로부터의 거리를 계산해서 거리가 1인 노드들 방문->2인 노드들 방문->3인 노드들 방문 이런 식으로 표현된다.

 

#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 함수 정의

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

#BFS 함수 호출

bfs(graph, 1, visited)

 

코딩테스트 준비하기

2022.12.18 - [Data Science] - [코딩테스트] 코딩테스트 및 관련 알고리즘의 개요

2022.12.19 - [Data Science] - [코딩테스트] 파이썬 문법 기초 복습 : 자료형

2022.12.20 - [Data Science] - [코딩테스트] 파이썬 문법 기초 복습 : 입출력부터 자주 쓰이는 라이브러리까지

2022.12.23 - [Data Science] - [코딩테스트] 그리디 알고리즘(Greedy), 탐욕법

2022.12.24 - [Data Science] - [코딩테스트] 구현, 시뮬레이션과 완전 탐색 
 
https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC 
*내용에 대한 모든 저작권은 해당 영상의 원저작자에게 있습니다.