[알고리즘] DFS/BFS

공부 : 동빈나 유튜브 < 3. DFS & BFS > + 책 < 이것이 취업을 위한 코딩테스트다 >

 

탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

- DFS/BFS는 대표적은 그래프 탐색 알고리즘

 

(사전 학습) 자료구조 정리

자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조

- 삽입(Push) / 삭제(Pop) 

- Overflow와 Underflow를 신경쓰기

 

1. 스택

- 선입후출(First In Last Out) / 후입선출(Last In First Out) 구조

- 파이썬에서 별도의 라이브러리 없이 리스트로 구현 가능

stack = []

#순서대로 5 2 3 7 삽입 - 삭제 - 1 4 삽입 - 삭제
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7) 
stack.pop() #7이 삭제
stack.append(1)
stack.append(4)
stack.pop() #4가 삭제

print(stack[::-1]) #스택의 최상단 원소부터 출력

 

2. 큐

- 선입선출(First In First Out)

- 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화 가능

- collection 모듈에서 제공하는 deque 자료구조 사용

- deque는 스택과 큐의 장점을 모두 채택한 것

- 리스트로도 구현이 가능하지만 deque를 사용하는 것에 비해 시간 복잡도가 높다.

- queue 라이브러리를 이용하는 것보다 간단하다.

from collections import deque

queue = deque()

#순서대로 5 2 3 7 삽입 - 삭제 - 1 4 삽입 - 삭제
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft() #5 삭제
queue.append(1)
queue.append(4)
queue.popleft() #2 삭제

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

 

+ 재귀함수 - 자기 자신을 다시 호출하는 함수

- 컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용

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

- 재귀함수가 반복문보다 유리할 수도 있고 불리할 수도 있다.

# 재귀함수를 이용한 팩토리얼 예제

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

print(factorial_recursive(5))

 

(재귀함수) 최대공약수 계산 (유클리드 호제법) 예제

유클리드 호제법

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

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

# 두 개의 자연수에 대한 최대공약수 구하기
# 유클리드 호제법

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

print(gcd(192, 162))

 

+ 그래프

노드(Node)와 간선(Edge)로 표현, 노드를 정점(Vertex)라고도 부름

- 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것

- 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'라고 표현

 

프로그래밍에서 그래프는 크게 2가지 방식으로 표현 가능

- 인접 행렬(Adjacency Matrix)

: 메모리가 불필요하게 낭비 / 정보를 인접 리스트보다 빠르게 얻음

INF = 999999999 #무한의 비용선언

#2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

 

- 인접 리스트(Adjacency List) : 연결 리스트 이용

: 메모리 효율적 사용 / 정보를 인접 방식보다 느리게 얻음

#행이 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(Depth-First-Search)

- 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

 - 스택 자료구조를 기초로 한다, O(N)

#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)

#index 0을 사용하지 않는 방향으로 코드 작성됨
# 각 노드가 연결된 정보 표시
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
#각 노드가 방문된 정보를 표현(1차원리스트)
visited = [False] * 9

#정의된 DFS 함수 호출
dfs(graph, 1, visited)

 

 

BFS(Breadth-First-Search)

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

- 큐 자료구조를 이용한다, O(N)
- 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편

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

#index 0을 사용하지 않는 방향으로 코드 작성됨
# 각 노드가 연결된 정보 표시
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)

---

예제

1. 음료수 얼려먹기

- 처음에 띄어쓰기 없이 받을 때 split을 쓰면 안된다 !!!!!

#00011 int로 받기
list(map(int, input()))

#문자로 각각 받기
list(input())

 

- 결국 한 블록을 찾을 때는 2중 for문이 들어갔다.

- 내가 짠 코드는 BFS로 조금 복잡/ 유튜브에서는 DFS로 재귀함수를 사용해서 간단한 느낌

 

2. 미로 탈출

- 미로찾기이기 때문에 BFS로 코드를 작성하는게 맞는 것 같다.

- 근데 나는 DFS로 짰다.

--> 벽이나 범위를 넘어갈 경우에 최대값으로 99999를 설정했다. 이렇게 하는것보다는 BFS가 더 정확한 느낌

 

코드 정리 : https://github.com/mingxoxo/Algorithm/tree/master/study/BFS_DFS

GitHub - mingxoxo/Algorithm: 알고리즘