탐색(search)
그래프(graph)
그래프 탐색
대표적인 그래프 탐색 알고리즘
# 스택 구현을 위해 파이썬의 기본 자료형인 리스트를 활용
stack = []
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack) #1-3-2-5
print(stack[::-1]) #5-2-3-1
from collections import deque
# 큐 구현을 위해 파이썬의 deque 라이브러리 활용
queue = deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) #3-7-1-4
queue.reverse() #역순으로 변환
print(queue) #4-1-7-3
*c++은 queue 자료구조 사용. append() 대신 push(), popleft() 대신 pop(), 단순 추출은 front()
*java도 queue 자료구조 사용. append() 대신 offer(), popleft() 대신 poll()
def factorial(n):
if n==1: # 또는 n<=1
return 1
return n * factorial(n-1)
factorial(6) #6!=6*5*4*3*2*1
ex. GCD(192, 162)두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 정의하였을 때, A와 B의 최대공약수는 R과 B의 최대공약수와 같음.
def gcd(a,b):
if a%b == 0 :
return b
return gcd(b,a%b)
DFS는 깊이 우선 탐색이라고도 불리며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
DFS는 스택 알고리즘 또는 재귀함수를 이용하며, 구체적인 동작과정은 아래와 같음
➡️ 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문처리를 함
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문처리하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
dfs 구현 예제
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,visited)
➡️ 동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문처리를 함
- 큐에서 노드를 꺼낸뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start]=True
# queue가 빌 때까지 반복
while queue:
v= queue.popleft()
# 현재 노드와 인접한 노드들을 모두 방문
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
# 정의된 dfs 호출
dfs(graph,1,visited)