Python 알고리즘 공부 (4: DFS/BFS)

DFS, BFS 는 대표적인 그래프 탐색 알고리즘이다. (탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다) DFS, BFS 에 대해 공부하기 위해 우선 몇 가지 자료구조에 대해 알아본다.

 

 

 

스택 자료구조라는 것이 있다. 스택 자료구조는 먼저 들어온 데이터가 나중에 나가는 선입후출의 자료구조를 갖는다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. Python 에서 stack 에 데이터를 추가할 때는 append 함수, 원소를 삭제할 때는 pop 함수를 사용한다.

 

 

 

다음으로는 큐 자료구조가 있다. 큐는 먼저 들어 온 데이터가 먼저 나가는 선입선출의 자료구조를 갖는다. 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있다. Python 에서 큐 자료구조를 활용하기 위해 collections 모듈로부터 deque 를 import 한다. (queue = deque() 로 큐 자료구조 객체를 만들어줌) append 로 자료를 추가, popleft() 함수로 원소를 삭제한다. 

 

 

 

또 재귀함수라는 것에 대해 알아봐야 한다. 재귀함수 (Recursive Function) 란 자기 자신을 다시 호출하는 함수를 의미한다. (파이썬에는 최대 재귀 깊이가 설정되어 있어서 단순히 무한하게 실행되게 하면 에러가 난다) 일반적으로는 재귀함수를 사용할 때는 종료 조건을 명시해주어야 한다. 재귀함수를 효과적으로 사용할 수 있는 방법 중 하나로, 최대공약수를 계산하는데 쓰이는 유클리드 호제법이 있다. 유클리드 호제법에 대한 설명은 아래와 같다.

 

 

• 두 자연수 A, B 에 대하여 (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)

 

 

 

위처럼 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다. 모든 재귀함수는 이론적으로 반복문을 이용하여 동일한 기능을 구현할 수 있으며, 재귀함수가 반복문보다 유리한 경우도, 불리한 경우도 있다. 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓이게 되는데, 그래서 스택을 사용할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.

 

 

 

이제 DFS (Depth First Search) 에 대해서 알아본다. DFS 는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS 는 스택 자료구조(혹은 재귀함수)를 이용하며 구체적인 동작 과정은 아래와 같다.

 

 

 

DFS

 

 

• 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
• 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
• 3. 더 이상 2 번의 과정을 수행할 수 없을 때까지 반복한다.

 

 

이를 Python 코드로 구현해보자면 아래와 같다.

 

 

 

graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]
visited = [False] * 9

def dfs(graph, v, visited):
  visited[v] = True
  print(v, end= " ")
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)


dfs(graph, 1, visited)

 

 

result

 

 

 

다음으로 BFS (Breadth-First Search) 는 너비 우선 탐색이라고도 불리며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS 는 큐 자료구조를 이용하며 구체저인 동작과정은 아래와 같다.

 

 

• 1. 탐색 시작 노드에 큐를 삽입하고 방문처리를 한다.
• 2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
• 3. 더 이상 2 번의 과정을 수행할 수 없을 때까지 반복한다.

 

 

이를 코드로 구현해보면 아래와 같다.

 

 

 

from collections import deque

graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]
visited = [False] * 9

def bfs(graph, start, visited):
  queue = deque([start])
  visited[start] = True
  while queue:
    v = queue.popleft()
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

bfs(graph, 1, visited)

 

 

 

이제 위 DFS, BFS 의 이론을 활용하여 실전 문제를 풀어본다. 

 

 

 

문제 1)

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

 

 

 

풀이 1)

위 문제는 DFS 로 해결할 수 있다. DFS 를 활용하는 알고리즘은 다음과 같다.

 

 

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤 주변 지점 중에서 값이 0 이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보며 방문을 진행하는 과정을 반복하면 연결된 모든 지점을 방문할 수 있다.
3. 모든 노드에 대하여1 ~ 2 번 과정을 반복하며 방문하지 않은 지점의 수를 카운트한다.

 

 

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

graph = []
for i in range(n):
  graph.append(list(map(int, input())))

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

result = 0
for i in range(n):
  for j in range(m):
    if dfs(i, j) == True:
      result += 1

print(result)

 

 

 

문제 2)

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

 

 

풀이 2)

BFS 를 활용한다. BFS 는 시작 지점에서 가까운 노드부터 차례대로 모든 노드를 탐색한다. 상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1 로 동일하기에 (1, 1) 지점부터 BFS 를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결할 수 있다.

 

 

 

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]

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]

print(bfs(0, 0))

 

 

 

 

 

 

Reference:

이것이 취업을 위한 코딩 테스트다