열렬히.뛰기

BFS: 너비 우선 탐색

알고리즘: 이론 > 알고리즘 : 그래프 (심화) > BFS: 너비 우선 탐색

  • 그래프로 되어있는 자료를 탐색하는 방법

DFS : 깊이 우선 탐색

1은 2로, 2는 3으로, 3은 4로. 다시 1에서 5로, 5는 6으로, 6은 7로.

가지 한개를 완전히 타고, 옆 가지를 완전히 타고…이 과정의 반복이다.

dfs 함수 만들기

1. 재귀 이용

python
visited = []
def dfs(n, graph, visited):
	for i in graph[n]:
		if i not in visited:
			visited.append(i)
			dfs(i, graph, visited)
  • dfs의 파라미터로는 시작점(n), 그래프(graph), 방문여부 체크 배열(visited)을 넣어준다.
  • 그래프의 시작점 속 숫자들을 하나하나 꺼내며 visited에 있는지 체크한다.
  • 만약, 그 숫자가 그래프에 없다면 그 숫자가 다시 시작점이 되서 또 다른 dfs에 들어가게 된다. (재귀함수)

이 과정을 반복하면 visited를 꽉 채울 수 있게 되며, 이는 그래프를 다 돌았다는 것을 의미한다.

2. 스택 이용

python
from collections import deque
def dfs(graph, start):
    visited = []
    queue = deque([start])   

    while queue:
        node = queue.pop() 
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
		return visited

BFS : 너비 우선 탐색

1 다음 2,3,4. 그리고 5,6,7,8. 그리고 9, 10

4층, 3층, 2층… 이런 순으로 내려온다고 생각하면 된다.

BFS 함수 만들기

1. 큐 자료구조 사용Ⅰ(유향그래프)

python
from collections import deque
visited = [False] * n

def bfs(graph, start, visited):
	queue = deque([start])
	visited[start] = True

	while queue:
		n = queue.popleft()
		for i in graph[n]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True

# n = 전체 정점(vertex)의 갯수

2. 큐 자료구조 사용 Ⅱ (인접행렬)

python
from collections import deque

def bfs(graph, start):
	queue = deque([])
	queue.append([x, y])

	while queue:
		x, y = queue.popleft()  # 가로, 세로 위치 꺼내기 
		graph[x][y] = -1        # 해당 행렬 값 변환
		for i in range(?):
			nx = x + dx[i]
			ny = y + dy[i]

			if nx < 0 or nx >= len(graph) or ny < 0 or ny >= len(graph):
					continue

			if graph[nx][ny] == 1:
					graph[nx][ny] == 0
					queue.append(nx, ny)

언제 쓰이는가?

DFS는

  1. 모든 노드를 방문하고자 하는 경우
  2. 경로의 특징을 저장하는 문제

    • 각 정점마다 숫자가 적혀있고, a~b까지 가는 경로를 구할 때 경로에

      같은 숫자가 있으면 안 된다는 문제인 경우

  3. 검색 대상의 그래프가 정~말로 큰 경우

반면 BFS는

  1. 모든 노드를 방문하고자 하는 경우
  2. 최단 거리 구하는 문제
  3. 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않은 경우