DFS, BFS

다음에 풀어볼 백준 문제는 DFS, BFS 와 관련된 것인데 처음 들어보는 것이라 공부를 해보았다.
( 참고 : https://youtu.be/7C9RgOcvkvo )

1. 스택과 큐

스택 : 선입 후출, 입구와 출구가 동일한 형태로 스택을 시각화한다.
파이썬에서는 append()와 pop() 메소드를 이용하면 스택 구현이 가능하다.
print(stack[::-1]) 최상단부터 출력, print(stack) 최하단부터 출력할 수 있다.
c++에서는 push()와 pop()으로 구현할 수 있다.

큐 : 선입 선출, 입구와 출구가 모두 뚫려있는 터널 형태로 스택을 시각화한다.
from collections import deque => 큐 구현을 위해 deque 라이브러리를 사용한다.
코드를 작성할 때, ‘queue = deque()’로 deque 객체 생성이 필수다.
이 라이브러리를 사용하면, append()와 popleft() 메소드를 이용하면 스택 구현이 가능하다.
print(queue) 먼저 들어온 순 출력, queue.reverse() print(queue) 나중에 들어온 순으로 출력할 수 있다.

2. 재귀 함수: 자기 자신을 다시 호출하는 함수

예시)

def recursive_function():
	print(“재귀함수 호출”)
	recursive_fuction()
recursive_function()

하지만 이렇게 재귀 함수를 작성하면 무한으로 반복되게 된다.
재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 명시해야 한다.

3. DFS, BFS

예시로 구현할 그래프

DFS : 깊이 우선 탐색, 스택 or 재귀 함수를 이용한다.

DFS 구현 순서
1) 탐색 시작 노드를 스택에 삽입 후 방문 처리
2) 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.
     방문하지 않은 인접한 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.
3) 더이상 2번이 진행되지 않을때까지 반복한다.

def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
	visited[v] = True
	print(v, end=‘ ‘)
	# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
	[],
	[2, 3, 8],
	[1, 7],
	[1, 4, 5],
	[3, 5],
	[3, 4],
	[7],
	[2, 6, 8],
	[1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visted)

실행 결과 : 1 2 7 6 8 3 4 5

BFS : 너비 우선 탐색, 가까운 노드부터 우선적으로 탐색한다. 큐를 이용한다.

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

각 프로그래밍 언어마다 큐를 어떻게 구현하는지 숙지할 필요가 있다.

from collections import deque

def bfs(graph, start, visited):
	# 큐 구현을 위해 deque 라이브러리 사용
	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

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
	[],
	[2, 3, 8],
	[1, 7],
	[1, 4, 5],
	[3, 5],
	[3, 4],
	[7],
	[2, 6, 8],
	[1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

실행 결과: 1 2 3 8 7 4 5 6