Post

[알고리즘] 깊이우선탐색, 넓이우선탐색(DFS, BFS)

Posted
By Ennik 18 min read
bfs dfs gif
  • 그래프의 모든 노드를 방문하기 위한 알고리즘
  • 루트 노드(혹은 다른 임의의 노드)에서 시작해, 다음 분기(branch)로 넘어가기 전에 해당 분기를 최대한 깊게 탐색한다.
  • 스택(Stack)을 사용하거나 재귀적 방법을 통해 구현한다.
  • 재귀적 방법을 통해 DFS를 사용할 경우, 파이썬에서는 재귀 호출의 깊이가 제한되어 있으므로 필요한 경우 sys.setrecursionlimit()을 사용하여 이 제한을 늘릴 수 있다.

DFS 알고리즘의 기본 절차

  1. 노드 방문: 시작 노드를 방문하고, 방문한 노드를 스택에 푸시(push)하며 방문 처리를 한다.
  2. 인접 노드 탐색: 현재 노드에 인접한 노드 중에서 방문하지 않은 노드를 하나 선택하고, 그 노드를 방문한다. 방문한 노드를 스택에 푸시하고 방문 처리 한다.
  3. 더 이상 탐색할 노드가 없을 때까지 반복: 현재 노드에 방문하지 않은 인접 노드가 더 이상 없다면, 스택에서 최상위 노드를 팝(pop)하여 빼내고, 그 노드를 현재 노드로 설정한다. 이 과정을 스택이 비워질 때까지 반복한다.
  4. 모든 노드 방문: 스택이 비워지면 탐색을 종료한다.

DFS 알고리즘 구현 예시 - 재귀 (Python)

다음 코드는 그래프에서 ‘A’ 노드부터 시작하여 DFS 방식으로 모든 노드를 탐색하고, 방문한 노드를 출력한다. visited 집합은 방문한 노드를 기록하여, 이미 방문한 노드를 다시 방문하지 않도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# DFS 알고리즘 구현 (재귀적 방식)
def dfs(graph, node, visited):
    # 현재 노드를 방문 처리
    visited.add(node)
    print(node, end=' ')

    # 현재 노드의 인접 노드를 확인하고, 방문하지 않은 노드를 DFS로 재귀적으로 방문
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 간단한 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 방문한 노드를 저장할 집합
visited = set()

# 'A'에서 시작하는 DFS 실행
dfs(graph, 'A', visited)

DFS 알고리즘 구현 예시 - Stack (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

def dfs_with_stack(graph, start_node):
    # 방문한 노드를 저장할 집합
    visited = set()
    # DFS를 위한 스택, 시작 노드를 포함하여 초기화
    stack = [start_node]

    # 스택이 비어있지 않는 동안 반복
    while stack:
        # 스택에서 하나의 노드를 꺼냄
        node = stack.pop()
        # 현재 노드를 방문하지 않았다면
        if node not in visited:
            # 방문 처리
            visited.add(node)
            print(node, end=' ')

            # 현재 노드에 인접한 노드 중 방문하지 않은 노드들을 스택에 추가
            # 여기서는 인접 노드를 거꾸로 스택에 추가하여, 그래프의 자연스러운 순서대로 방문하게 함
            stack.extend([x for x in graph[node] if x not in visited])

# 간단한 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 'A'에서 시작하는 DFS 실행
dfs_with_stack(graph, 'A')
  • 그래프의 모든 노드를 방문하기 위한 알고리즘
  • 루트 노드(혹은 다른 임의의 노드)에서 시작하여 인접한 모든 노드를 먼저 탐색한다.
  • 큐(Queue)를 사용하여 구현할 수 있으며, 이는 각 노드를 방문할 때마다 해당 노드와 인접한 노드를 큐에 추가하고, 큐에서 노드를 하나씩 꺼내어 그 노드의 인접 노드를 탐색하는 방식으로 진행된다.

BFS 알고리즘의 기본 절차

  1. 노드 방문: 시작 노드를 큐에 삽입하고 방문 처리한다.
  2. 인접 노드 탐색: 큐에서 노드를 하나 꺼내어 그 노드의 인접 노드를 모두 확인한다. 방문하지 않은 인접 노드를 모두 큐에 삽입하고 방문 처리한다.
  3. 탐색 반복: 큐가 비어있을 때까지 이전 과정을 반복한다.
  4. 모든 노드 방문 완료: 큐가 비어있으면 탐색을 종료한다.

BFS 알고리즘 구현 예시 - Queue (Python)

다음 코드는 시작 노드 ‘A’부터 BFS 방식으로 그래프를 탐색하고, 방문한 노드를 출력한다. deque를 사용하여 큐를 구현하고, 방문하지 않은 인접 노드를 순서대로 큐에 추가함으로써 너비 우선 탐색을 진행한다. 이 방식은 각 레벨의 모든 노드를 탐색한 후 다음 레벨의 노드를 탐색하는 방식으로, 가장 가까운 노드부터 차례대로 탐색한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

from collections import deque

# BFS 알고리즘 구현
def bfs(graph, start_node):
    # 방문한 노드를 저장할 집합
    visited = set()
    # BFS를 위한 큐, 시작 노드를 포함하여 초기화
    queue = deque([start_node])

    # 큐가 비어있지 않는 동안 반복
    while queue:
        # 큐에서 하나의 노드를 꺼냄
        node = queue.popleft()
        # 현재 노드를 방문하지 않았다면
        if node not in visited:
            # 방문 처리
            visited.add(node)
            print(node, end=' ')

            # 현재 노드에 인접한 노드 중 방문하지 않은 노드들을 큐에 추가
            queue.extend([x for x in graph[node] if x not in visited])

# 간단한 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 'A'에서 시작하는 BFS 실행
bfs(graph, 'A')

최단경로

  • 최단 경로 탐색: BFS는 시작 노드로부터 가까운 노드부터 차례대로 탐색하기 때문에, 목표 노드에 도달했을 때 그 경로가 최단 경로임이 보장된다. 즉, BFS는 레벨별로 탐색하기 때문에 모든 가능한 경로 중 가장 짧은 경로를 찾아낼 수 있다.

  • 효율성: DFS는 목표 노드를 찾기 위해 가능한 모든 경로를 탐색할 수 있으며, 이는 최단 경로를 찾는 문제에서 비효율적일 수 있다. DFS를 사용하면 길이 막힌 경로를 따라 깊숙이 탐색할 수 있으며, 결국에는 되돌아와 다른 경로를 탐색해야 할 수도 있다. 특히 큰 미로에서 많은 시간을 소비하게 될 수 있다.

  • 경로 길이 계산: BFS는 시작점으로부터의 거리(즉, 경로 길이)를 자연스럽게 계산할 수 있다. 각 단계에서 모든 인접 노드는 이전 단계의 노드로부터 한 칸 더 멀리 있으므로, 탐색의 각 단계는 시작점으로부터의 거리에 대한 정보를 제공한다. 반면, DFS는 경로의 길이를 추적하기 위해 추가적인 처리가 필요할 수 있다.

DFS & BFS 탐색 알고리즘 문제

백준 1012: 유기농 배추

  • 문제 설명
    • 직사각형 땅에 배추가 심어진 땅과 심어지지 않은 땅의 좌표가 주어진다.
    • 배추흰지렁이는 인접한 배추로 자유롭게 이동할 수 있고, 인접한 위치는 상하좌우를 의미한다.
    • 배추흰지렁이가 모든 배추로부터 보호받을 수 있도록 필요한 최소의 지렁이 수를 구한다.
  • 풀이
    • 입력 받은 배추 위치 정보를 바탕으로 그래프(또는 2차원 배열)를 구성한다.
    • 모든 배추 위치에 대해 탐색을 시작하고, 이미 방문한 위치는 다시 방문하지 않도록 한다.
    • 탐색 과정에서 상하좌우로 이동하고, DFS, BFS를 이용한다.(아래 코드에서는 DFS, stack 이용)
    • 필요한 최소 배추흰지렁이의 마리 수를 나타내는 카운터를 탐색을 시작할 때마다 1 증가시킨다.
    • 각 테스트 케이스에 대해 계산된 배추흰지렁이의 마리 수를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

import sys

def dfs(x, y, field, visited):
  # 스택 초기화 및 시작 노드 추가
  stack = [(x, y)]
  while stack:
    (x, y) = stack.pop()
    # 현재 위치를 방문 처리
    if visited[y][x] == False:
      visited[y][x] = True
      # 상하좌우 네 방향에 대해 탐색
      for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx, ny = x + dx, y + dy
        # 필드 안에 있고, 방문하지 않았으며, 배추가 심어져 있는지 확인
        if 0 <= nx < m and 0 <= ny < n and not visited[ny][nx] and field[ny][nx] == 1:
          stack.append((nx, ny))


t = int(sys.stdin.readline())
for _ in range(t):
  # 배추밭의 가로길이 m, 세로길이 n, 배추 위치의 개수 k
  m, n, k = map(int, sys.stdin.readline().split())
  field = [[0] * m for _ in range(n)]  # 배추밭 초기화
  visited = [[False] * m for _ in range(n)]  # 방문 여부 체크 초기화

  # 배추 위치 입력 받기
  for _ in range(k):
    x, y = map(int,sys.stdin.readline().split())
    field[y][x] = 1  # 배추 위치를 1로 표시

  # 필요한 지렁이 수 초기화
  worms = 0

  for i in range(n):
    for j in range(m):
      if field[i][j] == 1 and not visited[i][j]:
        dfs(j, i, field,visited)
        worms += 1

  print(worms)

백준 2178: 미로 탐색

  • 문제 설명
    • N × M 크기의 배열로 표현되는 미로가 주어진다.
    • 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.
    • 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
    • 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구한다.
  • 풀이
    • 최단거리를 계산하는데에는 bfs가 적절하기 때문에, bfs를 이용한다.
    • 입력받은 정보를 바탕으로 미로를 구성하고, 방문여부와 이동한 칸 수를 저장하는 배열을 만든다.
    • 이전 노드의 이동한 칸 수로부터 1을 더하면 현재 노드로의 이동한 칸 수가 된다.
    • bfs를 통해 이동하면서, 목표지점에 도달하면 반복문을 종료하고 구하는 값을 반환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import sys
from collections import deque

# 미로의 크기 N(행), M(열)을 입력받음
n, m = map(int, sys.stdin.readline().split())

# 미로의 상태를 입력받아 저장하는 리스트. '1'은 이동 가능, '0'은 이동 불가능한 칸을 의미
maze = [sys.stdin.readline()[0:-1] for _ in range(n)]

# 각 칸의 방문 여부를 저장하는 2차원 리스트. 모든 값은 False로 초기화
visited = [[False] * m for _ in range(n)]

# 시작점으로부터 각 칸까지 도달하는 데 필요한 최소 이동 횟수를 저장하는 2차원 리스트
count = [[0] * m for _ in range(n)]

def bfs(graph, visited, count):
    # 시작 위치 (0, 0)를 방문 처리하고, 시작점의 이동 횟수를 1로 설정
    visited[0][0] = True
    count[0][0] = 1

    # BFS 탐색을 위한 큐 초기화 및 시작 위치 추가
    queue = deque([(0, 0)])

    # 큐가 빌 때까지 BFS 탐색 수행
    while queue:
        # 큐에서 현재 위치를 꺼냄
        v = queue.popleft()

        # 현재 위치에서 상하좌우로 이동할 위치를 계산
        for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = v[0] + dx, v[1] + dy

            # 이동할 위치가 미로 내부에 있고, 아직 방문하지 않았으며, 이동 가능한 칸일 경우
            if 0 <= nx < m and 0 <= ny < n and not visited[ny][nx] and maze[ny][nx] == '1':
                # 이동할 위치를 큐에 추가하고 방문 처리
                queue.append((nx, ny))
                visited[ny][nx] = True

                # 이동 횟수 갱신: 현재 위치의 이동 횟수 + 1
                count[ny][nx] = count[v[1]][v[0]] + 1

                # 목적지에 도달했다면, 최소 이동 횟수를 반환
                if ny == n - 1 and nx == m - 1:
                    return count[ny][nx]

# BFS 함수를 호출하여 결과(최소 이동 횟수) 출력
print(bfs(maze, visited, count))
0.1 자료구조 · 알고리즘
Algorithm Search
This post is licensed under CC BY 4.0 by the author.