[알고리즘] 3. DFS&BFS(나동빈 2021 이코테)

https://www.youtube.com/watch?v=7C9RgOcvkvo&t=2871s 

- 탐색: 많은 양의 데이터 중 원하는 데이터를 찾는 과정

 

- 스택: 먼저 들어온 데이터가 나중에 나가는 형식(선입후출) 입구=출구

           -> python은 append(넣기) pop(빼기)

stack = []
stack.append(5) #index 0
stack.append(2)
stack.append(3)
stack.append(7)

stack.pop() #원소 7 삭제

print(stack) #[5,2,3]

- 큐: 먼저 들어온 데이터가 먼저 나가는 형식(선입선출) 줄서는거!

       -> python은 deque 라이브러리 불러오기/ append와 popleft

from collections import deque

queue = deque() #queue 구현을 위해 deque 라이브러리 사용

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft() #가장 왼쪽 원소(5) 삭제

print(queue) #[2,3,7]

- 유클리드 호제법(최대공약수 계산)

자연수 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) #b랑 a%b(나머지)를 나눈 게 0이 될 때까지 재귀~

print(gcd(192, 162))

 

- DFS: 깊이 우선 탐색(깊은 부분 우선적으로 탐색) STACK 이용

def dfs(graph, v, visited):

    visited[v] = True #현재 노드를 방문 처리
    
    print(v, end=' ')

    for i in graph[v]: #graph[v]는 v 지점과 인접한 노드들 [2,3,8]
        if not visited[i]: #지점 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: 너비 우선 탐색(가까운 노드 우선적으로 탐색하는 알고리즘) QUEUE 이용 => 최단 경로

       -> 처음 노드 큐에 넣고, 꺼내고 인접한 노드 한번에 큐에 넣기 -> 순서대로 하나 꺼내고 인접한 노드 한번에 큐에 넣기 -> 반복 

from collections import deque

def bfs(graph, start, visited):

    queue = deque([start])
    visited[start] = True

    while queue: #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)