[Python][알고리즘] 이코테 강의정리 - DFS & BFS

스택과 큐 자료구조

- 스택 구현 예제

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

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

- 큐 구현 예제

: 이것도 리스트를 이용해서 짤 수도 있지만 시간복잡도가 더 증가 => deque 라이브러리 이용하기!

from collections import deque

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

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력([3,7,1,4])
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력([4,1,7,3])

재귀 함수

: DFS를 간결하고 짧은 코드로 작성하기 위해 사용(스택 라이브러리 대신 재귀 함수를 이용하는 경우)

- 간단 예시

def recursive_function():
    print('재귀 함수를 호출합니다.')
    recursive_function()
    
recursive_function()	# 무한 루프

- 팩토리얼 구현 예제

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result=1
    for i in range(1, n+1):
        result*=i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
    if n<=1:
        return 1
    return n * factorial_recursive(n-1)

print('반복적으로 구현:', factorial_iterative(5))   # 반복적으로 구현: 120
print('재귀적으로 구현:', factorial_recursive(5))   # 재귀적으로 구현: 120

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

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

DFS(Depth-First Search)

• 깊이 우선 탐색
• 스택 자료구조(혹은 재귀함수)를 이용

- 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)
            
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)	# 실행결과 : 1 2 7 6 8 3 4 5

BFS(Breadth-First Search)

• 너비 우선 탐색 / 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조 이용
• 각 간선의 비용이 모두 동일한 상황에서 최단거리 문제를 해결하기 위한 목적으로 사용

- 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
                
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)	# 실행 결과 : 1 2 3 8 7 4 5 6

기초 문제 예제

- 음료수 얼려 먹기 문제(DFS or BFS)

def dfs(x, y):
    if x<=-1 or x>=n or y<=-1 or y>=m:
        return False
    if graph[x][y]==0:
        graph[x][y]=1
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False

n, m = map(int, input().split())

graph=[]
for i in range(n):
    graph.append(list(map(int, input())))
    
result = 0
for i in range(n):
    for j in range(m):
        if dfs(i,j)==True:
            result+=1
            
print(result) 

- 미로 탈출 문제(BFS)

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny]==0:
                continue
            if graph[nx][ny]==1:
                graph[nx][ny]=graph[x][y]+1
                queue.append((nx, ny))
                
    return graph[n-1][m-1]


from collections import deque

n, m = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
# 이동할 네 가지 방향 정의(상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

print(bfs(0,0))