[이코테] DFS & BFS

본 포스팅은 유투브에 온라인 배포되어 있는 나동빈 님의 이코테 강의를 수강하며 정리한 내용을 기록한 것입니다. 자세한 내용이 궁금하다면, 링크를 참고하시길 바랍니다.

 

포스팅 내 코드 블록은 깃허브에서 찾을 수 있음.

 

꼭 필요한 자료구조 기초

스택 (Stack)

• 선입후출, 입구 == 출구.
• 컴퓨터에서 함수 호출 시 실행되는 구조와 유사함
• list로 구현 가능

# stack

stack = []      # 스택 생성
stack.append(v) # 스택에 데이터 삽입
stack.pop()     # 스택에서 데이터 꺼내기

 

 

큐 (queue)

• FIFO(선입선출). 터널 구조
• 시간복잡도를 위해 deque(덱)을 사용하는 것이 적절함

# queue
from collections import deque

queue = deque() # 큐 생성
queue.append(v) # 큐에 데이터 삽입
queue.popleft() # 큐에서 데이터 꺼내기

 

재귀 알고리즘 (Recursive algorithm)

• 함수 내에서 자기 자신을 호출하는 알고리즘
• 모든 재귀 알고리즘은 반복문으로 구성이 가능함

대표적인 예로는 유클리드 호제법이 있음. 최대공약수(GCD)를 구하기 위한 방법 중 하나

 

DFS

• Depth-First Search 의 약어. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료 구조 혹은 재귀 함수를 통해 구현 가능함
• 구체적인 동작 과정
  1. 탐색 시작 노드를 스택에 삽입. 방문 처리
  2. 스택에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 인접 노드가 있으면, 그 노드를 스택에 넣고 방문 처리
  3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
  4. 2,3 과정을 수행할 수 없을 때까지 반복

 

재귀를 통해 구현한 DFS

# DFS - recursive
def dfs2(v):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

 

스택을 통해 구현한 DFS

# DFS - stack
def dfs3(graph, stack, visited):
    while stack:
        v = stack.pop()
        if visited[v]: continue  # 꺼낼 때 방문 체크
        visited[v] = True
        print(v, end=' ')
        for i in graph[v][::-1]:
            if not visited[i]:
                stack.append(i)

 

 

BFS

• Breadth-First Search의 약어. 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용함
• 구체적인 동작 과정
  1. 탐색 시작 노드를 큐에 삽입. 방문 처리
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 모든 인접 노드를 큐에 삽입하고 방문 처리
  3. 더 이상 2를 수행할 수 없을 때까지 반복

 

덱을 통해 구현한 BFS (시간복잡도를 고려하여 deque을 사용하는 것이 좋음)

# BFS - deque
from collections import deque
def bfs(graph, queue, visited):
while queue:
v = queue.popleft()
if visited[v]: continue
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
visited[i] = True  # 넣을 때 방문 체크
queue.append(i)

 

 

문제 풀이

1. 얼음 깨기 문제

문제 풀이 전략

- 연결 요소의 개수를 찾는 문제로 DFS, BFS 상관없이 아무 방법을 사용하여 연결 요소를 찾음

# 문제: 음료수 얼려먹기
n, m = list(map(int, input().split(' ')))

frame = []
for _ in range(n):
    frame.append(input())

def dfs(frame, node, visited):
    i, j = node

    if i<0 or i>=n or j<0 or j>=m:
        return
    else:
        if not visited[i][j] and (frame[i][j] == '0'):
            visited[i][j] = 1 
            dfs(frame, (i+1, j), visited)
            dfs(frame, (i-1, j), visited)
            dfs(frame, (i, j+1), visited)
            dfs(frame, (i, j-1), visited)

visited = [[0 for _ in range(m)] for _ in range(n)]
answer = 0 
for i in range(n):
    for j in range(m):
        if (not visited[i][j]) and (frame[i][j] == '0'):
            dfs(frame, (i, j), visited)
            answer += 1

print(answer)

 

2. 미로 찾기 문제

 

문제 풀이 전략

- 최단 거리를 찾는 것이 목적이므로 BFS를 활용하여 접근

- visited를 maze 위에 기록하면 리소스를 아끼고 효과적으로 구성할 수 있음 (ndb 전략을 따름)

from collections import deque
def solution(n,m,maze):
    queue = deque([(0,0)])
    dirs = ((1,0), (-1,0), (0,1), (0,-1))

    while queue:
        v = queue.popleft()
        if (v[0] == n-1) and (v[1] == m-1):
            return maze[v[0]][v[1]]
        for dx,dy in dirs:
            nx,ny = v[0]+dx,v[1]+dy
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if maze[nx][ny] == 1:
                maze[nx][ny] += maze[v[0]][v[1]]
                queue.append((nx,ny))

if __name__ == '__main__':
    n,m = 5,6 
    maze = [[1,0,1,0,1,0], [1,1,1,1,1,1], [0,0,0,0,0,1], [1,1,1,1,1,1], [1,1,1,1,1,1]]
    ans = 10
    print(solution(n,m,maze), ans)