[Algorithm] DFS/BFS 알고리즘과 예시

 

오늘은 알고리즘 중에서도 어렵다고 유명한 DFS와 BFS에 대해 공부해 보려고 합니다.

그런데 막상 공부하고 보니 이 두 알고리즘은 일단 외우고 시작하는 게 가장 좋은 것 같습니다.

실제로 이와 비슷한 문제를 마주치면 이 알고리즘을 구현해 놓고 수정하는 방법으로 진행해도 좋을 것 같습니다.

 

 

---

 

 

1. DFS(Depth-First-Search, 깊이 우선 탐색)

그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.

구현은 아래와 같이 하면 됩니다.

 

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)

 

 

위에서 입력으로 주어지는 graph는 각 행별로 0,1,2,3.. 번호에 인접해 있는 번호를 나타냅니다.

예를 들어 1번은 2, 3, 8번과 이어져 있고, 5번은 3, 4번과 이어져 있다고 보면 됩니다.

아래 그림과 같은 형태입니다.

그래서 문제에서 저러한 꼴로 입력이 주어지지 않아도 저러한 형식으로 입력을 변환한 뒤 문제를 해결해 나가면 됩니다.

 

 

DFS

 

 

 

---

2. BFS(Breadth First Search, 너비 우선 탐색)

가까운 노드부터 탐색하는 알고리즘입니다.
일반적인 경우 수행시간이 DFS보다 좋은 편입니다.

구현은 다음과 같습니다.

BFS에서는 queue의 개념을 사용하여 구현합니다.

 

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)

 

 

※ 일반적으로 경로를 기억해야 하는 문제의 경우 DFS를, 최단 거리를 구하는 경우 BFS를 사용합니다.

 

이와 관련된 문제를 몇 가지 더 풀어보도록 합시다..

 

 

 

---

3. 음료수 얼려먹기

 

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

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

def dfs(x, y):
  if x < 0 or x >= n or y < 0 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("answer : ", result)

4 5

00110

00011

11111

00000

answer : 3

 

 

 

---

4. 미로탈출

 

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 ny < 0 or nx >= n 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("answer : ", bfs(0, 0))

5 6

101010

111111

000001

111111

111111

answer : 10