[코딩테스트] DFS/BFS 알고리즘

DFS/BFS

탐색 알고리즘

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

 

stack : LIFO (후입선출)

-> python에서는 리스트와 append(), pop()을 통해 쉽게 stack의 삽입/삭제 연산을 구현 가능

 

queue : FIFO (선입선출)

-> python에서 큐 규현을 위한 라이브러리 사용

from collections import deque

queue = deque() # 큐 구현

queue.append(5) # 오른쪽에 값 추가
queue.append(4)
queue.append(3)
queue.popleft() # 왼쪽에 값 제거 -> 5 제거

queue.reverse() # 역순으로 바꾸기

 

 

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

DFS 구현 시 자주 사용되는 방법

스택의 기법처럼 호출된 함수를 하나씩 저장하다가 맨 마지막에 호출된 함수가 가장 먼저 꺼짐 

-> 스택 구현 대신에 재귀 함수를 이용할 수 있음

 

유클리드 호제법 : 최대공약수를 계산하는 알고리즘

R = A % B (A > B)

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

2단계 A는 1단계의 B, 2단계의 B는 1단계의 A%B

12는 6의 배수이므로, 이때 최대 공약수는 6이라고 할 수 있음

def gcd(a, b):
    if a % b == 0: # a가 b의 배수라면
        return b
    else:
        return gcd(b, a % b) # 재귀함수

gcd(192, 162)

 

 

DFS (Depth First Search) : 깊이 우선 탐색 알고리즘

1. 탐색 시작 노드를 스택에 삽입 후 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있다면, 해당 노드를 스택에 넣고 방문 처리

-> 낮은 번호를 우선 처리

3. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼냄

4. 3번이 수행 불가능할 때까지 반복

(※ 가장 낮은 숫자부터 방문하는 것으로 가정, 시작 숫자는 1)

스택에 1을 넣음

최상단 스택(1)에 인접 노드 중 가장 작은 수인 2를 스택에 넣고 방문 처리

최상단 스택(2)에 인접 노드 중 가장 작은 수인 7를 스택에 넣고 방문 처리

최상단 스택(7)에 인접 노드 중 가장 작은 수인 6를 스택에 넣고 방문 처리

최상단 스택(6)에 인접 노드가 없으므로 스택에서 제거

최상단 스택(7)에 인접 노드 중 가장 작은 수인 8를 스택에 넣고 방문 처리

....

 

- 그래프 구현 시

1. 각 노드에 연결된 노드 번호를 연결 리스트를 통해 표현

-> 일반적으로 1부터 노드가 시작되므로 0번 인덱스는 비워두는 것이 효과적

2. 방문 여부를 판단하는 visited 리스트를 구현

 

- 코드 예제

# 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) # 재귀 호출

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
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)

DFS는 스택에 기초함 -> 실제 구현에는 스택을 쓸 필요 없음

DFS는 재귀함수를 사용함

 

 

BFS (Breadth First Search) : 너비 우선 탐색 알고리즘

그래프에서 가까운 노드부터 우선 탐색

큐 자료구조를 사용함

1. 탐색 시작 노드를 큐에 삽입 후 방문 처리

2. 큐에서 노드를 꺼내고, 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리

-> 인접한 노드를 한 번에 큐에 넣고, 방문처리하는 것이 특징

(※ 가장 낮은 숫자부터 방문하는 것으로 가정, 시작 숫자는 1)

큐에 1을 넣음

노드를 하나 꺼내고(1), 해당 노드에 인접한 모든 노드를 큐에 삽입(2, 3, 8) 후, 방문 처리

노드를 하나 꺼내고(2), 해당 노드에 인접한 모든 노드를 큐에 삽입(7) 후, 방문 처리

노드를 하나 꺼내고(3), 해당 노드에 인접한 모든 노드를 큐에 삽입(4, 5) 후, 방문 처리

노드를 하나 꺼내고(8), 해당 노드에 인접한 노드 중 방문하지 않은 노드가 없으므로 무시

 

- 코드 예제

from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

BFS는 큐를 사용함

반복문을 통해서 제어

 

 

예제) 연결요소 찾기 문제

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 # 방문 처리
        # 상화좌우 단순방문처리, return 처리 결과는 사용하지 않음
        dfs(x-1, y) # 상
        dfs(x+1, y) # 하
        dfs(x, y-1) # 좌
        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를 통해 해결 가능

-> 1,1 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하여 해결

 

bfs (x, y):
    q = deque()
    q.append(x, y)
    while q:
        x, y = q.popleft()
  
        for i in range(4): # 주변 노드(상하좌우) 모두 탐색
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or ny < 0 or nx >= n or ny >= n: # 공간을 벗어나는 경우
                continue
            if graph[nx][ny] == 0: # 벽인 경우
                continue
            if graph[nx][ny] == 1: # 처음 방문하는 노드인 경우
                graph[nx][ny] = graph[x][y] + 1 # 현재 방문 노드 거리에 따라 거리 값 갱신
                q.append((nx, ny)) # queue에 노드 추가
    return graph[n-1][m-1]

 

 

 

 

※ 해당 포스트는 이것이 "코딩 테스트다 with 파이썬(나동빈 저)"를 통해 학습한 내용을 정리한 것입니다.