DFS & BFS

[dev-onejun]

Stack Example

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.pop()

# -> stack = [5, 2]

print(stack[::-1]) # 최상단 원소부터 출력 -> [2, 5]
print(stack) # 최하단 원소부터 출력 -> [5, 2]

[dev-onejun]

Queue Example

You can use list as queue, but using deque is more benefits for time complexity.

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft()

# -> queue = [2, 3]

print(queue) # 먼저 들어온 순서대로 출력 -> [2, 3]

queue.reverse()
print(queue) # 나중에 들어온 원소부터 출력 -> [3, 2]

[dev-onejun]

Recursive Function

NOTE

• Python has the limit of depth of recursive function as default. So if you just ran a code plainly, the program will be stopped automatically with RecursionError.
• All the iteration can be the recursive function, vice versa.
• Because a called function, the recursive function, is allocated in computer memory as a stack, it uses instead of the stack as it makes codes briefly.

Example

Factorial

def factorial(n):
    if n <= 1:
        return 1

    return n * factorial(n-1)

print(factorial(5)) # -> 120

Euclidean Algorithm

the method of computing the Greatest Common Divisor (GCD) of two integers, the largest number that divides them both without a remainder.

def gcd(a, b):
    r = a % b

    if r == 0:
        return b

    return gcd(b, r)

print(gcd(192, 162)) # -> 6

[dev-onejun]

Algorithm

DFS (Depth-First Search)

def dfs(graph, v, visited): # v는 현재 방문한 노드
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[v]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
    [], # 보통 그래프 문제에서 0번 노드로 시작하지 않기 때문에 비워둠.
    [2, 3, 8], # 1번 노드는 2,3,8번 노드와 간선이 있음.
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9 # -> [False, False, ..., False]

dfs(graph, 1, visited) # -> 1 2 7 6 8 3 4 5

BFS (Breadth-First Search)

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(graph, 1, visited) # visited는 False로 초기화 했다고 가정. -> 1 2 3 8 7 4 5 6

[dev-onejun]

연습문제

음료수 얼려 먹기

[dev-onejun]

Idea

1. use bfs to make the ice-cream first

[dev-onejun]

미로 탈출

[dev-onejun]

Idea

because we should find the shortest path of the player, using bfs will work.