DFS, BFS

DFS와 BFS는 모두 그래프를 탐색하기 위한 방법이다. 즉, 그래프를 탐색하기 위해 DFS나 BFS를 모두 사용할 수 있지만 탐색할 다음 노드를 결정할 때 두 방식의 동작이 다르다. 이 때문에 사용하는 방법에도 차이가 있다.

그래프

node, vertex weight (가중치)

그래프의 컴퓨터 표현

• 그냥 edge(간선) 만 저장
  • 간선 정보만 저장하면, 노드와 노드 간 인접 정보를 알기 어려운 단점
• 인접 행렬
  • 공간복잡도가 O(N^2) 인 단점
  • 특정 노드 두 개의 연결 여부는 매우 빠르게 확인 가능
• 인접 리스트
  • 공간복잡도 : O(sum(adjacent_nodes))

edge = [[] for i in range(n+1)]

for i in range(m):
	a, b = map(int, input().split())

	edge[a].append(b)
	edge[b].append(a)

1 : [2, 3]
2 : [1, 3]
3 : [1, 2]
4 : [5]
5 : [4]

세 표현 방식은 한 그래프에 대해 동치이며, 서로 전환할 수 있다.

DFS

# 방문처리
visited = [False for i in range(n)]
def dfs(cur):
	visited[cur] = True
	
	for i in range(len(edge)):
		nxt = edge[cur][i]
		if visited[nxt]: continue
		dfs(nxt)


dfs(1)

모두 다 방문되면 끝남 $\rightarrow$ 각 노드를 한 번씩만 방문하게 됨 visited 배열을 살펴보면, 연결 요소 간 관계를 알 수 있다.

백트래킹의 경우 $\rightarrow$ 모든 경로를 탐색하므로 visited를 해제함

격자로 표현된 그래프와 DFS

격자 한 칸을 노드, 갈 수 있는 방향을 간선으로 보면 격자 문제를 그래프 탐색으로 풀 수 있음

def dfs(x, y):
	visited[x][y] = True

	for i in range(2):
		nx = x + dx[i]
		ny = y + dy[i]

		if (nx < 0 or nx >= N or
			ny < 0 or ny >= M or 
			arr[nx][ny] == 1  or 
			visited[nx][ny]): 
			continue
		
		dfs(nx, ny)

BFS 탐색

• 재귀 없이 짬
• queue 사용
• 큐에 넣을 때 방문처리 해줘야 함

queue = deque()
visited = [False for i in range(n+1)]

queue.append(1)
visited[1] = True

while len(queue) > 0:
	cur = queue[0]
	que.popleft()

	for nxt in edge[cur]:
		if visited[nxt]:
			continue

		queue.append(nxt)
		visited[nxt] = True

• BFS 특징
  • 시작점부터 거리 순으로 퍼져나감
  • 따라서 이동거리 추적이 가능

queue = deque()
visited = [False for i in range(n+1)]
dist = [-1 for i in range(n+1)]
queue.append(1)
visited[1] = True
dist[1] = 0
while len(queue) > 0:
	cur = queue[0]
	que.popleft()

	for nxt in edge[cur]:
		if visited[nxt]:
			continue

		queue.append(nxt)
		dist[nxt] = dist[cur] + 1
		visited[nxt] = True